Query complexity of stochastic minimum vertex cover

DOI10.4230/LIPICS.ITCS.2025.41MaRDI QIDQ7296678zbMATH OpenFDO

Authors Mahsa Derakhshan, Mohammad Saneian, Zhiyang Xun

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.41

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A new proof of the graph removal lemma
• A two-pass (conditional) lower bound for semi-streaming maximum matching
• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• Monotonicity testing over general poset domains
• On graphs decomposable into induced matchings of linear sizes
• On regularity lemma and barriers in streaming and dynamic matching
• On sparsification of stochastic packing problems
• Shortest‐path metric approximation for random subgraphs
• Stochastic matching on uniformly sparse graphs
• Stochastic matching with few queries: (1-ε) approximation
• Stochastic minimum vertex cover in general graphs: a 3/2-approximation
• Stochastic packing integer programs with few queries
• Stochastic vertex cover with few queries
• Stochastic weighted matching: (1- ) approximation
• Towards a unified theory of sparsification for matching problems

Cited in

(1)

• One-way communication complexity of minimum vertex cover in general graphs

This page was built for publication: Query complexity of stochastic minimum vertex cover

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