Linear-time parameterized algorithms with limited local resources

DOI10.1016/j.ic.2022.104951OpenAlexW3010618012MaRDI QIDQ2105436

Ying Guo, Qin Huang, Jian'er 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)

Related Items (1)

Space limited graph algorithms on big data

Uses Software

• Pregel

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On graph problems in a semi-streaming model
• Streaming Kernelization
• Undirected single-source shortest paths with positive integer weights in linear time
• Sublinear Time Algorithms
• Data Structures for Weighted Matching and Extensions to b -matching and f -factors
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Kernelization
• The Power of Linear-Time Data Reduction for Maximum Matching
• Dynamic Parameterized Problems and Algorithms
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Maximum matching and a polyhedron with 0,1-vertices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Towards a theory of parameterized streaming algorithms

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