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:
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
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