Linear-time parameterized algorithms with limited local resources

DOI10.1016/J.IC.2022.104951MaRDI QIDQ2105436zbMATH OpenOpenAlexFDO

Authors Ying Guo, Qin Huang, Jianer Chen

Publication date 8 December 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.02866

zbMATH Keywords

graph matchingspace complexitylinear-time algorithmbigdata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• The Power of Linear-Time Data Reduction for Maximum Matching
• The power of linear-time data reduction for maximum matching
• Data Reduction for Maximum Matching on Real-World Graphs
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Data streams: algorithms and applications.
• Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors
• Dynamic parameterized problems and algorithms
• Introduction to algorithms.
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Kernelization. Theory of parameterized preprocessing
• Maximum matching and a polyhedron with 0,1-vertices
• On graph problems in a semi-streaming model
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Streaming algorithms for estimating the matching size in planar graphs and beyond
• Streaming kernelization
• Sublinear time algorithms
• The Power of Linear-Time Data Reduction for Maximum Matching
• Towards a theory of parameterized streaming algorithms
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(3)

• Constant-Time Local Computation Algorithms
• Space limited graph algorithms on big data
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data

Describes a project that uses

Uses Software

• Pregel

This page was built for publication: Linear-time parameterized algorithms with limited local resources

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