Linear-time algorithms for three domination-based separation problems in block graphs
| Autor: | Annegret Wagler, Silvia M. Bianchi, Gabriela R. Argiroffo, Yanina Lucarini |
|---|---|
| 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: |
Computational complexity theory
Locating-dominating and open locating-dominating codes Applied Mathematics 0211 other engineering and technologies Block graphs 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Graph Computational complexity 010201 computation theory & mathematics Chordal graph Bipartite graph Discrete Mathematics and Combinatorics Identifying Time complexity Algorithm Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Applied Mathematics Discrete Applied Mathematics, 2020, 281, pp.6-41. ⟨10.1016/j.dam.2019.08.001⟩ Discrete Applied Mathematics, Elsevier, 2020, 281, pp.6-41. ⟨10.1016/j.dam.2019.08.001⟩ |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.08.001⟩ |
| Popis: | International audience; The problems of determining minimum identifying, locating-dominating or open locating-dominating codes are special search problems that are challenging both from a theoretical and a computational point of view, even for several graph classes where other in general hard problems are easy to solve, like bipartite graphs or chordal graphs. Hence, a typical line of attack for these problems is to determine minimum codes of special graphs. In this work we study the problem of determining the cardinality of minimum such codes in block graphs (that are diamond-free chordal graphs). We present linear-time algorithms for these problems, as a generalization of a linear-time algorithm proposed by Auger in 2010 for identifying codes in trees. Thereby, we provide a subclass of chordal graphs for which all three problems can be solved in linear time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect