Identifying path covers in graphs

DOI10.1016/J.JDA.2013.07.006MaRDI QIDQ396675zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Matjaž Kovše

Publication date 13 August 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.07.006

zbMATH Keywords

identificationpathsapproximationtest cover

Mathematics Subject Classification ID

Approximation algorithms (68W25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• On the identification problems in products of cycles
• Optimal identifying codes in cycles and paths
• More results on the complexity of identifying problems in graphs
• Identifying vertex covers in graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• Approximation algorithms for combinatorial problems
• Approximation algorithms for the test cover problem
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
• Codes identifying sets of vertices in random networks
• Complexity of approximating bounded variants of optimization problems
• Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Extremal graphs for the identifying code problem
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Identifying codes in line graphs
• Induced subsets
• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• On a new class of codes for identifying vertices in graphs
• On the identification of vertices using cycles
• Structural properties of twin-free graphs
• Watching systems in graphs: an extension of identifying codes

Cited in

(10)

• Locating-domination and identification
• On Iiro Honkala's contributions to identifying codes
• Identifying vertex covers in graphs
• Graph covering via shortest paths
• Separating path systems of almost linear size
• Improved kernels for tracking paths
• On the path separation number of graphs
• Separating path systems for the complete graph
• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results

This page was built for publication: Identifying path covers in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396675)