Edge search in graphs with restricted test sets

DOI10.1016/J.DISC.2009.04.013MaRDI QIDQ1045083zbMATH OpenOpenAlexFDO

Authors Tatjana Gerzen

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

group testingcombinatorial searchedge searchinformation-theoretic bound

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Searching for an edge in a graph with restricted test sets
• Search problems on graphs
• A tight upper bound for group testing in graphs
• On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
• A search problem on graphs which generalizes some group testing problems with two defectives

Cites work

• scientific article; zbMATH DE number 3662840 (Why is no real title available?)
• scientific article; zbMATH DE number 15129 (Why is no real title available?)
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 2141600 (Why is no real title available?)
• A Method for Detecting All Defective Members in a Population by Group Testing
• A probabilistic upper bound for the edge identification complexity of graphs
• A tight upper bound for group testing in graphs
• Competitive group testing
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Searching for an edge in a graph with restricted test sets

Cited in

(14)

• An NP-completeness result of edge search in graphs
• Testing for edge terms is decidable
• On a combinatorial search problem
• A revised algorithm for searching for all defective edges in a graph
• On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
• Edge search in graphs and hypergraphs of bounded rank
• Searching for an edge in a graph with restricted test sets
• A group testing problem for graphs with several defective edges
• A competitive algorithm to find all defective edges in a graph
• A search problem on graphs which generalizes some group testing problems with two defectives
• A ternary search problem on graphs
• Group testing in graphs
• Search problems on graphs
• A tight upper bound for group testing in graphs

This page was built for publication: Edge search in graphs with restricted test sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1045083)