Combinatorial identification problems and graph powers

DOI10.1007/S10288-011-0167-7zbMATH Open1237.05048OpenAlexW2082763530MaRDI QIDQ766254FDOQ766254

David Auger

Publication date: 23 March 2012

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://pastel.archives-ouvertes.fr/pastel-00593649/file/theseDA4Juin.pdf

Recommendations

• More results on the complexity of identifying problems in graphs
• Codes Identifying Vertices in Graphs
• On a new class of identifying codes in graphs
• The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm
• On strongly identifying codes

zbMATH Keywords

algorithmsgraphsidentifying codesNP-complete problemspowers of graphsdistance in graphs

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Cites Work

• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On identifying codes
• On a new class of codes for identifying vertices in graphs
• Diameters in graphs
• Extremal cardinalities for identifying and locating-dominating codes in graphs

This page was built for publication: Combinatorial identification problems and graph powers

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