Learning spanning forests optimally in weighted undirected graphs with CUT queries

MaRDI QIDQ7017085zbMATH OpenFDO

Authors Deeparnab Chakrabarty, Hang Liao

Publication date 6 March 2025

Full work available at URL https://proceedings.mlr.press/v237/liao24b.html

zbMATH Keywords

cut-queriesquery algorithmsrandomized algorithmsweighted spanning forest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20)

Cites work

• A query algorithm for learning a spanning forest in weighted undirected graphs
• Computing exact minimum cuts without knowing the graph
• Dynamic graph connectivity in polylogarithmic worst case time
• Edge Estimation with Independent Set Oracles
• Faster randomized worst-case update time for dynamic subgraph connectivity
• Graph connectivity and single element recovery via linear and OR queries
• scientific article; zbMATH DE number 1508646 (Why is no real title available?)
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• scientific article; zbMATH DE number 7788397 (Why is no real title available?)
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Learning a Hidden Matching
• Learning a Hidden Subgraph
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Minimizing symmetric submodular functions
• Near-optimal massively parallel graph connectivity
• Nearly optimal edge estimation with independent set queries
• New Query Lower Bounds for Submodular Function Minimization
• Non-adaptive edge counting and sampling via bipartite independent set queries
• On parity check \((0, 1)\)-matrix over \(\mathbb{Z}_p\)
• On the ``log rank-conjecture in communication complexity
• Optimal lower bounds for distributed and streaming spanning forest computation
• Optimal query complexity bounds for finding graphs
• Optimal reconstruction of graphs under the additive model
• Optimally reconstructing weighted graphs using queries
• Parallel graph connectivity in log diameter rounds
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Toward a deterministic polynomial time algorithm with optimal additive query complexity
• Weighted min-cut: sequential, cut-query, and streaming algorithms

Cited in

(3)

• Realizing graphs with cut constraints
• Learning partitions using rank queries
• Cut-query algorithms with few rounds

This page was built for publication: Learning spanning forests optimally in weighted undirected graphs with CUT queries

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