Linear-time parameterized algorithms with limited local resources

DOI10.1016/J.IC.2022.104951OpenAlexW3010618012MaRDI QIDQ2105436FDOQ2105436

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

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

zbMATH Keywords

graph matchingspace complexitylinear-time algorithmbigdata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Introduction to algorithms.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Maximum matching and a polyhedron with 0,1-vertices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Sublinear time algorithms
• Data streams: algorithms and applications.
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• On graph problems in a semi-streaming model
• Undirected single-source shortest paths with positive integer weights in linear time
• Kernelization. Theory of parameterized preprocessing
• Streaming kernelization
• 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
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Streaming algorithms for estimating the matching size in planar graphs and beyond
• Towards a theory of parameterized streaming algorithms
• The Power of Linear-Time Data Reduction for Maximum Matching
• Dynamic parameterized problems and algorithms

Cited In (3)

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

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)