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

algorithmsdistance in graphsgraphsidentifying codesNP-complete problemspowers of graphs

Mathematics Subject Classification ID

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

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)