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

DOI10.1007/978-3-662-53174-7_32zbMath1417.05207MaRDI 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

05C12: Distance in graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Metric Dimension of Bounded Tree-length Graphs, More results on the complexity of identifying problems in graphs, Complexity of metric dimension on planar graphs, Edge monitoring problem on interval graphs, Parameterized and approximation complexity of \textsc{Partial VC Dimension}, 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, Computing a metric basis of a 2-connected bipartite distance-hereditary graph, Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity

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