Parameterized Streaming: Maximal Matching and Vertex Cover

DOI10.1137/1.9781611973730.82MaRDI QIDQ5363104zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, Graham Cormode, Morteza Monemizadeh, Mohammad T. Hajiaghayi

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.82

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Recommendations

• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Streaming deletion problems Parameterized by vertex cover
• Streaming deletion problems parameterized by vertex cover
• scientific article; zbMATH DE number 6678937
• Better streaming algorithms for the maximum coverage problem
• scientific article; zbMATH DE number 6905172
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• On estimating maximum matching size in graph streams
• Approximate Maximum Matching in Random Streams
• Streaming algorithms for estimating the matching size in planar graphs and beyond

Cited in

(29)

• Dynamic graph stream algorithms in \(o(n)\) space
• Fixed parameter tractability of graph deletion problems over data streams
• Linear-time parameterized algorithms with limited local resources
• An estimator for matching size in low arboricity graphs with two applications
• Streaming deletion problems parameterized by vertex cover
• Parameterized analysis and crossing minimization problems
• scientific article; zbMATH DE number 6678937 (Why is no real title available?)
• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• Brief announcement: MapReduce algorithms for massive trees
• Independent sets in vertex-arrival streams
• Optimality of linear sketching under modular updates
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Approximate Maximum Matching in Random Streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Streaming deletion problems Parameterized by vertex cover
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Space limited graph algorithms on big data
• Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
• Space limited linear-time graph algorithms on big data
• Parameterized complexity of streaming diameter and connectivity problems
• Improved bounds for matching in random-order streams
• Improved bounds for matching in random-order streams
• Weighted matching in the random-order streaming and robust communication models
• Parameterized complexity of streaming diameter and connectivity problems
• Maximum coverage in the data stream model: parameterized and generalized
• Parameterized quantum query algorithms for graph problems
• Parameterized streaming algorithms for topological sorting
• Almost optimal superconstant-pass streaming lower bounds for reachability
• Polynomial kernels with reachability for weighted d-matroid intersection

This page was built for publication: Parameterized Streaming: Maximal Matching and Vertex Cover

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