Searching for an edge in a graph with restricted test sets

DOI10.1016/j.disc.2008.01.055zbMath1172.68047OpenAlexW1979139202MaRDI QIDQ1024439

Tatjana Gerzen

Publication date: 17 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.01.055

zbMATH Keywords

graphssearch problemsedge searchgroup testing problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges ⋮ An NP-completeness result of edge search in graphs ⋮ Edge search in graphs with restricted test sets

Cites Work

• Competitive group testing
• A probabilistic upper bound for the edge identification complexity of graphs
• A Method for Detecting All Defective Members in a Population by Group Testing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Searching for an edge in a graph with restricted test sets