Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity

DOI10.1007/s00453-016-0184-1zbMath1371.05212arXiv1405.2424OpenAlexW3101038336WikidataQ56551560 ScholiaQ56551560MaRDI QIDQ2408094

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

Publication date: 9 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.2424

zbMATH Keywords

complexityinterval graphresolving setmetric dimensionidentifying codelocating-dominating setpermutation graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ Vertex identification in trees ⋮ Complexity of metric dimension on planar graphs ⋮ Metric Dimension of Bounded Width Graphs ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters ⋮ On finding the best and worst orientations for the metric dimension ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ On three domination-based identification problems in block graphs ⋮ Complexity of maximum cut on interval graphs ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ On the irregularity of \(\pi \)-permutation graphs, Fibonacci cubes, and trees ⋮ Unnamed Item ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Centroidal localization game ⋮ Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Discriminating Codes in Geometric Setups ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Sequential metric dimension ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Metric dimension parameterized by treewidth ⋮ Characterizing extremal graphs for open neighbourhood location-domination ⋮ Metric dimension of maximal outerplanar graphs ⋮ Locating-Domination and Identification ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ Metric-locating-dominating sets of graphs for constructing related subsets of vertices ⋮ Bounding the trace function of a hypergraph with applications ⋮ Hardness of metric dimension in graphs of constant treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Locating-total domination in graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• Network verification via routing table queries
• On separating systems
• On minimum metric dimension of honeycomb networks
• Minimal identifying codes in trees and planar graphs with large girth
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Bipartite permutation graphs
• 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.
• Powers of geometric intersection graphs and dispersion algorithms
• Resolvability in graphs and the metric dimension of a graph
• A simple linear time algorithm for cograph recognition
• Algorithmic graph theory and perfect 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
• Induced subsets
• Landmarks in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
• On the Complexity of Metric Dimension
• Metric Dimension Parameterized by Max Leaf Number
• Metric Dimension of Bounded Width Graphs
• Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
• Identifying and Locating–Dominating Codes in (Random) Geometric Networks
• On locating and differetiating-total domination in trees
• Domination and location in acyclic graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Graph Classes: A Survey
• On a new class of codes for identifying vertices in graphs
• How complex are random graphs in first order logic?
• Reducibility among Combinatorial Problems
• Identifying Codes in Line Graphs
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity