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

DOI10.1007/978-3-642-35926-2_4zbMath1293.05365MaRDI QIDQ2876554

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

identification; paths; approximation; test cover

Mathematics Subject Classification ID

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Identifying path covers in graphs