Linear-time algorithms for three domination-based separation problems in block graphs - Université Clermont Auvergne Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2020

Linear-time algorithms for three domination-based separation problems in block graphs

Résumé

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.
Fichier principal
Vignette du fichier
ABLW_block_hal.pdf (330.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03154751 , version 1 (01-03-2021)

Identifiants

Citer

Gabriela Argiroffo, Silvia Bianchi, Yanina Lucarini, Annegret K Wagler. Linear-time algorithms for three domination-based separation problems in block graphs. Discrete Applied Mathematics, 2020, 281, pp.6-41. ⟨10.1016/j.dam.2019.08.001⟩. ⟨hal-03154751⟩
32 Consultations
92 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More