An NP-completeness result of edge search in graphs

DOI10.1007/s00373-013-1287-yzbMath1293.05367OpenAlexW2075281130MaRDI QIDQ2014718

Tatjana Gerzen

Publication date: 16 June 2014

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-013-1287-y

zbMATH Keywords

NP-completenessgroup testing problemcombinatorial searchedge search

Mathematics Subject Classification ID

Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cites Work

• On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
• Searching for an edge in a graph with restricted test sets
• Edge search in graphs with restricted test sets
• A probabilistic upper bound for the edge identification complexity of graphs
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An NP-completeness result of edge search in graphs