Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
From MaRDI portal
Publication:2408094
DOI10.1007/S00453-016-0184-1zbMATH Open1371.05212DBLPjournals/algorithmica/FoucaudMNPV17arXiv1405.2424OpenAlexW3101038336WikidataQ56551560 ScholiaQ56551560MaRDI QIDQ2408094FDOQ2408094
Authors: Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov 
Publication date: 9 October 2017
Published in: Algorithmica (Search for Journal in Brave)
Abstract: We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted IDENTIFYING CODE, (OPEN) LOCATING-DOMINATING SET and METRIC DIMENSION) of an interval or a permutation graph. In these problems, one asks to distinguish all vertices of a graph by a subset of the vertices, using either the neighbourhood within the solution set or the distances to the solution vertices. Using a general reduction for this class of problems, we prove that the decision problems associated to these four notions are NP-complete, even for interval graphs of diameter and permutation graphs of diameter . While IDENTIFYING CODE and (OPEN) LOCATING-DOMINATING SET are trivially fixed-parameter-tractable when parameterized by solution size, it is known that in the same setting METRIC DIMENSION is -hard. We show that for interval graphs, this parameterization of METRIC DIMENSION is fixed-parameter-tractable.
Full work available at URL: https://arxiv.org/abs/1405.2424
Recommendations
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
- On metric-location-domination number of graphs
- On metric dimension of permutation graphs
- On the strong metric dimension of permutation graphs
- scientific article; zbMATH DE number 2192146
- On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
- A note on the complexity of locating-total domination in graphs
- On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
- The fractional metric dimension of permutation graphs
complexitymetric dimensionresolving setidentifying codeinterval graphlocating-dominating setpermutation graph
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Graph Classes: A Survey
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- 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
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Induced subsets
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On identifying codes
- Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
- On a new class of codes for identifying vertices in graphs
- Identifying codes in line graphs
- Title not available (Why is that?)
- Minimal identifying codes in trees and planar graphs with large girth
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bipartite permutation graphs
- Treewidth. Computations and approximations
- Landmarks in graphs
- On the Complexity of Metric Dimension
- Title not available (Why is that?)
- Locating-total domination in graphs
- On minimum metric dimension of honeycomb networks
- Title not available (Why is that?)
- On the Complexity of Canonical Labeling of Strongly Regular Graphs
- Computing the metric dimension for chain graphs
- Metric dimension of bounded width graphs
- Title not available (Why is that?)
- On locating and differetiating-total domination in trees
- Domination and location in acyclic graphs
- The (weighted) metric dimension of graphs: hard and easy cases
- On separating systems
- A simple linear time algorithm for cograph recognition
- Title not available (Why is that?)
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Title not available (Why is that?)
- Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
- Metric dimension parameterized by max leaf number
- Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
- Identifying codes in hereditary classes of graphs and VC-dimension
- Identifying and locating-dominating codes in (random) geometric networks
- How complex are random graphs in first order logic?
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Approximability of identifying codes and locating-dominating codes
- Network verification via routing table queries
- Graph-Theoretic Concepts in Computer Science
- Powers of geometric intersection graphs and dispersion algorithms
Cited In (34)
- Discriminating Codes in Geometric Setups
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Complexity of maximum cut on interval graphs
- Identifying codes in hereditary classes of graphs and VC-dimension
- Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
- Paired-domination problem on distance-hereditary graphs
- On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
- On three domination-based identification problems in block graphs
- Locating-domination and identification
- On the irregularity of \(\pi \)-permutation graphs, Fibonacci cubes, and trees
- Centroidal localization game
- Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
- Complexity of metric dimension on planar graphs
- Metric-locating-dominating sets of graphs for constructing related subsets of vertices
- Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
- Metric dimension parameterized by treewidth
- Characterizing extremal graphs for open neighbourhood location-domination
- Alternative parameterizations of \textsc{Metric Dimension}
- Linear-time algorithms for three domination-based separation problems in block graphs
- Extremal Digraphs for open neighbourhood location-domination and identifying codes
- On finding the best and worst orientations for the metric dimension
- Vertex identification in trees
- Title not available (Why is that?)
- Metric Dimension Parameterized by Treewidth in Chordal Graphs
- On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
- Metric dimension of bounded width graphs
- Metric dimension of maximal outerplanar graphs
- Complexity and approximation for discriminating and identifying code problems in geometric setups
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Sequential metric dimension
- Bounding the trace function of a hypergraph with applications
- Hardness of metric dimension in graphs of constant treewidth
- On three domination-based identification problems in block graphs
This page was built for publication: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408094)
