Combinatorial search in two and more rounds

DOI10.1016/j.tcs.2019.02.004zbMath1422.68057OpenAlexW2914299536MaRDI QIDQ2420609

Peter Damaschke

Publication date: 6 June 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.02.004

zbMATH Keywords

matchingtest coveradaptive strategycombinatorial search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterizations of test cover with bounded test sizes
• Rounds in combinatorial search
• A new strongly competitive group testing algorithm with small sequentiality
• Finding at least one excellent element in two rounds
• Improved sorting networks with O(log N) depth
• Bounds on the length of disjunctive codes
• A parameterized perspective on packing paths of length two
• Computing small partial coverings
• Sorting in \(c \log n\) parallel steps
• Approximation algorithms for the test cover problem
• (Non-)existence of polynomial kernels for the test cover problem
• Parameterized Study of the Test Cover Problem
• Partially Polynomial Kernels for Set Cover and Test Cover
• A Tighter Analysis of Set Cover Greedy Algorithm for Test Set
• Reducibility among Combinatorial Problems
• Zig-zag sort
• Optimal Two-Stage Algorithms for Group Testing Problems
• Optimal Sorting Networks
• Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes

This page was built for publication: Combinatorial search in two and more rounds