Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs

DOI10.1007/978-3-662-53174-7_32zbMath1417.05207OpenAlexW2483303513MaRDI QIDQ2827829

Petru Valicov, Aline Parreau, Florent Foucaud, Reza Naserasr, George B. Mertzios

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/16026/1/16026.pdf

Mathematics Subject Classification ID

Distance in graphs (05C12) 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)

Related Items (10)

More results on the complexity of identifying problems in graphs ⋮ Complexity of metric dimension on planar graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Edge monitoring problem on interval graphs ⋮ Computing a metric basis of a 2-connected bipartite distance-hereditary graph ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs ⋮ Bounding the trace function of a hypergraph with applications ⋮ Metric Dimension of Bounded Tree-length Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The (weighted) metric dimension of graphs: hard and easy cases
• On minimum metric dimension of honeycomb networks
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Treewidth. Computations and approximations
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Resolvability in graphs and the metric dimension of a graph
• Algorithmic graph theory and perfect graphs
• On powers of \(m\)-trapezoid graphs
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Computing the metric dimension for chain graphs
• Approximability of identifying codes and locating-dominating codes
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the Complexity of Metric Dimension
• Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
• Identifying and Locating–Dominating Codes in (Random) Geometric Networks
• Domination and location in acyclic graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• How complex are random graphs in first order logic?
• Identifying Codes in Line Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs