Binary search and recursive graph problems

DOI10.1016/S0304-3975(96)00266-6MaRDI QIDQ1391302zbMATH OpenFDO

Authors William Gasarch, Katia Guimarães

Publication date 22 July 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(96)00266-6

zbMATH Keywords

binary search probleminfinite recursive graph

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A binary search problem on graphs
• scientific article; zbMATH DE number 749657
• Binary search in graphs revisited
• Binary search in graphs revisited
• Unbounded search and recursive graph problems
• Deterministic and probabilistic binary search in graphs
• Search problems on graphs
• scientific article; zbMATH DE number 15129
• A ternary search problem on graphs

Cites work

• A proof of Beigel's cardinality conjecture
• An almost optimal algorithm for unbounded searching
• Effective coloration
• Effective Matchmaking and k-Chromatic Graphs
• scientific article; zbMATH DE number 3710117 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Recursively enumerable sets and degrees
• Terse, superterse, and verbose sets
• Unbounded Searching Algorithms

Cited in

(3)

• Unbounded search and recursive graph problems
• The complexity of finding SUBSEQ(A)
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case

This page was built for publication: Binary search and recursive graph problems

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