A probabilistic upper bound for the edge identification complexity of graphs

DOI10.1016/0012-365X(94)90178-3zbMath0803.68050OpenAlexW1986561909MaRDI QIDQ1322293

Eberhard Triesch

Publication date: 5 May 1994

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

Full work available at URL: https://doi.org/10.1016/0012-365x(94)90178-3

zbMATH Keywords

random graphedge identification complexity

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)

Related Items (4)

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 ⋮ Searching for an edge in a graph with restricted test sets ⋮ Edge search in graphs with restricted test sets

Cites Work

• Cliques in random graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: A probabilistic upper bound for the edge identification complexity of graphs