Polyhedra Associated with Open Locating-Dominating and Locating Total-Dominating Sets in Graphs
| Autor: | Silvia M. Bianchi, Yanina Lucarini, Annegret Wagler, Gabriela R. Argiroffo |
|---|---|
| Přispěvatelé: | Universidad Nacional de Rosario [Argentina], Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
open locating-dominating code problem
020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 16. Peace & justice locating total-dominating code problem 01 natural sciences Graph Combinatorics Minimum dominating set Polyhedron 010201 computation theory & mathematics polyhedral approach 0202 electrical engineering electronic engineering information engineering Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Combinatorial Optimization. ISCO 2020 Combinatorial Optimization. ISCO 2020, pp.3-14, 2020, Print 978-3-030-53261-1 / Online 978-3-030-53262-8. ⟨10.1007/978-3-030-53262-8_1⟩ Lecture Notes in Computer Science ISBN: 9783030532611 ISCO |
| DOI: | 10.1007/978-3-030-53262-8_1⟩ |
| Popis: | International audience; The problems of determining open locating-dominating or locating total-dominating sets of minimum cardinality in a graph G are variations of the classical minimum dominating set problem in G and are all known to be hard for general graphs. A typical line of attack is therefore to determine the cardinality of minimum such sets in special graphs. In this work we study the two problems from a polyhedral point of view. 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 such sets for special graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|