Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
From MaRDI portal
Publication:512651
DOI10.1016/j.tcs.2017.01.006zbMath1358.05216arXiv1507.08164OpenAlexW1921387904WikidataQ56551559 ScholiaQ56551559MaRDI QIDQ512651
Petru Valicov, Florent Foucaud, Aline Parreau, Reza Naserasr, George B. Mertzios
Publication date: 27 February 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.08164
Bounds on codes (94B65) Other types of codes (94B60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (17)
Identifying Codes in Hereditary Classes of Graphs and VC-Dimension ⋮ Vertex identification in trees ⋮ Truncated metric dimension for finite graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ 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 ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ On three domination-based identification problems in block graphs ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ Centroidal localization game ⋮ Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension ⋮ Sequential metric dimension ⋮ Characterizing extremal graphs for open neighbourhood location-domination ⋮ Metric dimension of maximal outerplanar graphs ⋮ Metric-locating-dominating sets of graphs for constructing related subsets of vertices ⋮ Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs ⋮ Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The (weighted) metric dimension of graphs: hard and easy cases
- Monadic second-order evaluations on tree-decomposable graphs
- Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
- On separating systems
- Minimal identifying codes in trees and planar graphs with large girth
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Bipartite permutation graphs
- 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
- A simple linear time algorithm for cograph recognition
- Identifying and locating-dominating codes on chains and cycles
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Induced subsets
- On the Complexity of Metric Dimension
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- Extremal Graph Theory for Metric Dimension and Diameter
- 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
- Graph Classes: A Survey
- On a new class of codes for identifying vertices in graphs
- Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
- How complex are random graphs in first order logic?
- Identifying Codes in Line Graphs
This page was built for publication: Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
