Combinatorial identification problems and graph powers

DOI10.1007/S10288-011-0167-7MaRDI QIDQ766254zbMATH OpenOpenAlexFDO

Authors 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

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)

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

Cites work

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

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)