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

DOI10.1007/978-3-642-35926-2_4zbMATH Open1293.05365OpenAlexW157345956MaRDI QIDQ2876554FDOQ2876554

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

Recommendations

• Identification of vertices of vertex-labeled graphs
• scientific article
• 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

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)

Cited In (3)

• Graph covering via shortest paths
• Identifying path covers in graphs
• 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)