Progress on the description of identifying code polyhedra for some families of split graphs
| Autor: | Silvia M. Bianchi, Annegret Wagler, Gabriela R. Argiroffo |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
021103 operations research identifying code problem Applied Mathematics 0211 other engineering and technologies Structure (category theory) 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Longest path problem Theoretical Computer Science Metric dimension Combinatorics Polyhedron Indifference graph Computational Theory and Mathematics 010201 computation theory & mathematics Chordal graph split graphs polyhedral approach Bipartite graph Search problem MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Optimization Discrete Optimization, Elsevier, 2016, 22, pp.225-240. ⟨10.1016/j.disopt.2016.06.002⟩ Discrete Optimization, 2016, 22, pp.225-240. ⟨10.1016/j.disopt.2016.06.002⟩ |
| ISSN: | 1572-5286 1873-636X |
| Popis: | International audience; The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs and split graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size. In this work we study the associated polyhedra for some families of split graphs: headless spiders and complete suns. We provide the according linear relaxations, discuss their combinatorial structure, and demonstrate how the associated polyhedra can be entirely described or polyhedral arguments can be applied to find minimum identifying codes for special split graphs. We discuss further lines of research in order to apply similar techniques to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect