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

DOI10.1016/j.dam.2019.08.001zbMath1440.05187OpenAlexW2971827493WikidataQ127297513 ScholiaQ127297513MaRDI QIDQ2184661

Annegret K. Wagler, Silvia M. Bianchi, Gabriela R. Argiroffo, Yanina P. Lucarini

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal.uca.fr/hal-03154751/file/ABLW_block_hal.pdf

zbMATH Keywords

computational complexityblock graphsidentifyinglocating-dominating and open locating-dominating codes

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph designs and isomorphic decomposition (05C51)

Related Items (2)

A linear-time algorithm for weighted paired-domination on block graphs ⋮ On three domination-based identification problems in block graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polyhedral approach to locating-dominating sets in graphs
• Algorithmic aspects of open neighborhood location-domination in graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Recent developments on graphs of bounded clique-width
• Minimal identifying codes in trees and planar graphs with large girth
• Distance-hereditary graphs
• On metric properties of certain clique graphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Polyhedra associated with identifying codes in graphs
• Identifying and locating-dominating codes on chains and cycles
• Linear time solvable optimization problems on graphs of bounded clique-width
• Computing the metric dimension for chain graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• A linear-time algorithm for the identifying code problem on block graphs
• Study of Identifying Code Polyhedra for Some Families of Split Graphs
• Identifying and Locating–Dominating Codes in (Random) Geometric Networks
• Domination and location in acyclic graphs
• On a new class of codes for identifying vertices in graphs

This page was built for publication: Linear-time algorithms for three domination-based separation problems in block graphs