On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths

DOI10.1007/978-3-642-35926-2_4MaRDI QIDQ2876554zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Matjaž Kovše

Publication date 19 August 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-35926-2_4

zbMATH Keywords

identificationpathsapproximationtest cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Identification of vertices of vertex-labeled graphs
• scientific article; zbMATH DE number 5360704
• Identifying path covers in graphs
• Recognizing \(k\)-path graphs
• More results on the complexity of identifying problems in graphs
• On a new class of codes for identifying vertices in graphs
• On the complexity of the identifiable subgraph problem
• On the characterization of path graphs
• On the complexity of the identifiable subgraph problem, revisited

Cited in

(4)

• Identifying path covers in graphs
• Identifying vertex covers in graphs
• Graph covering via shortest paths
• Improved kernels for tracking paths

This page was built for publication: On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths

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