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
complexityinterval graphresolving setmetric dimensionidentifying codelocating-dominating setpermutation graph
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
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