Edge search in graphs with restricted test sets

DOI10.1016/J.DISC.2009.04.013zbMATH Open1181.68174OpenAlexW1998478634MaRDI QIDQ1045083FDOQ1045083

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Competitive group testing
• Title not available (Why is that?)
• A Method for Detecting All Defective Members in a Population by Group Testing
• A probabilistic upper bound for the edge identification complexity of graphs
• Searching for an edge in a graph with restricted test sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A tight upper bound for group testing in graphs

Cited In (13)

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