On the Complexity of Finding an Unknown Cut Via Vertex Queries

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

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

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

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

   Recommendations

• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)