Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
type: Item
instance of: scholarly article
title: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
zbMATH Open document ID: 1371.05212
author: Florent Foucaud
author: George B. Mertzios
author: Reza Naserasr
author: Aline Parreau
author: Petru Valicov
published in: Algorithmica
publication date: 2017-10-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/1405.2424
full work available at URL: 19676.pdf
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6788764
zbMATH Keywords: metric dimension
zbMATH Keywords: resolving set
zbMATH Keywords: identifying code
zbMATH Keywords: locating-dominating set
zbMATH Keywords: interval graph
zbMATH Keywords: permutation graph
zbMATH Keywords: complexity
Wikidata QID: Q56551560
MaRDI profile type: Publication
OpenAlex ID: W3101038336
arXiv ID: 1405.2424
cites work: Powers of geometric intersection graphs and dispersion algorithms
cites work: Minimal identifying codes in trees and planar graphs with large girth
cites work: On the Complexity of Canonical Labeling of Strongly Regular Graphs
cites work: Network verification via routing table queries
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Metric Dimension of Bounded Width Graphs
cites work: Q4659582
cites work: On separating systems
cites work: Induced subsets
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
cites work: Graph Classes: A Survey
cites work: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
cites work: Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
cites work: Resolvability in graphs and the metric dimension of a graph
cites work: On locating and differetiating-total domination in trees
cites work: On identifying codes
cites work: Q3789614
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: On the Complexity of Metric Dimension
cites work: Fundamentals of parameterized complexity
cites work: Metric Dimension Parameterized by Max Leaf Number
cites work: The (weighted) metric dimension of graphs: hard and easy cases
cites work: Computing the metric dimension for chain graphs
cites work: Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
cites work: Identifying Codes in Line Graphs
cites work: Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
cites work: Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
cites work: Q4198056
cites work: Algorithmic graph theory and perfect graphs
cites work: Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
cites work: A simple linear time algorithm for cograph recognition
cites work: Q4119237
cites work: Locating-total domination in graphs
cites work: Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
cites work: Reducibility among Combinatorial Problems
cites work: On a new class of codes for identifying vertices in graphs
cites work: Landmarks in graphs
cites work: How complex are random graphs in first order logic?
cites work: Treewidth. Computations and approximations
cites work: On minimum metric dimension of honeycomb networks
cites work: Identifying and Locating–Dominating Codes in (Random) Geometric Networks
cites work: Q5710169
cites work: Q3279628
cites work: Q3565861
cites work: Q4075485
cites work: Domination and location in acyclic graphs
cites work: Q3803159
cites work: Bipartite permutation graphs
cites work: Approximability of identifying codes and locating-dominating codes
DBLP publication ID: journals/algorithmica/FoucaudMNPV17

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (DOI)
DOI: 10.1007/S00453-016-0184-1

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
Similarity Score: 0.9797605
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
Similarity Score: 0.96335423
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: Q5042540
Similarity Score: 0.8856822
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: On metric dimension of permutation graphs
Similarity Score: 0.88478106
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: On the strong metric dimension of permutation graphs
Similarity Score: 0.87563485
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: Q5463520
Similarity Score: 0.87010115
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
Similarity Score: 0.86689067
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: A note on the complexity of locating-total domination in graphs
Similarity Score: 0.8652508
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
Similarity Score: 0.8625859
Recommender Run: Recommender Run 3

Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity (Recommended article)
Recommended article: The fractional metric dimension of permutation graphs
Similarity Score: 0.86256874
Recommender Run: Recommender Run 3