Algorithmic aspects of open neighborhood location-domination in graphs

DOI10.1016/j.dam.2015.03.002zbMath1350.05124OpenAlexW269097313MaRDI QIDQ344871

Arti Pandey, B. S. Panda

Publication date: 24 November 2016

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

Full work available at URL: https://doi.org/10.1016/j.dam.2015.03.002

zbMATH Keywords

graph algorithmapproximation algorithmchordal graphNP-completedominationAPX-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Vertex degrees (05C07)

Related Items (4)

The adjacency dimension of graphs ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ Characterizing extremal graphs for open neighbourhood location-domination

Cites Work

• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Open neighborhood locating-dominating in trees
• Approximation hardness of dominating set problems in bounded degree graphs
• A survey of selected recent results on total domination in graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Some APX-completeness results for cubic graphs
• Incidence matrices and interval graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Dually Chordal Graphs
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithmic aspects of open neighborhood location-domination in graphs