On the Complexity of Finding an Unknown Cut Via Vertex Queries

DOI10.1007/978-3-540-73545-8_45zbMATH Open1213.68324OpenAlexW1502382854MaRDI QIDQ3608870FDOQ3608870

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

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

Mathematics Subject Classification ID

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

Cited In (4)

• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Approximating \(\alpha\)-cuts with the vertex method
• On the complexity of finding balanced oneway cuts
• Structural diagnosis of wiring networks: Finding connected components of unknown subgraphs

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)