On the Complexity of Finding an Unknown Cut Via Vertex Queries

DOI10.1007/978-3-540-73545-8_45MaRDI QIDQ3608870zbMATH OpenOpenAlexFDO

Authors Peyman Afshani, Ehsan Chiniforooshan, Reza Dorrigiv, Arash Farzan, Mehdi Mirzazadeh, Narges Simjour, Hamid Zarrabi-Zadeh

Publication date 6 March 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73545-8_45

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Computing exact minimum cuts without knowing the graph
• Optimal query complexity bounds for finding graphs
• Searching for an edge in a graph
• Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs
• Deterministic and probabilistic binary search in graphs

Cited in

(8)

• On the complexity of finding balanced oneway cuts
• Approximating -cuts with the vertex method
• Structural diagnosis of wiring networks: Finding connected components of unknown subgraphs
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs
• Computing exact minimum cuts without knowing the graph
• Optimal algorithms for finding connected components of an unknown graph
• Query complexity of global minimum cut

This page was built for publication: On the Complexity of Finding an Unknown Cut Via Vertex Queries

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