Space-efficient approximation scheme for maximum matching in sparse graphs

DOI10.4230/LIPICS.MFCS.2016.28zbMATH Open1398.05163OpenAlexW2543489815MaRDI QIDQ4608587FDOQ4608587

Authors: Samir Datta, Raghav Kulkarni, A. Mukherjee 

Publication date: 21 March 2018

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6443/pdf/LIPIcs-MFCS-2016-28.pdf/

Recommendations

• scientific article; zbMATH DE number 3965443
• Planar matching in streams revisited
• Approximation algorithms for weighted matching
• Computing large matchings in planar graphs with fixed minimum degree
• Computing large matchings in planar graphs with fixed minimum degree

zbMATH Keywords

planar graphsapproximation schememaximum matchinglogspace

Mathematics Subject Classification ID

Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (8)

• Improved induced matchings in sparse graphs
• Data Reduction for Maximum Matching on Real-World Graphs
• Simple 2^f-Color Choice Dictionaries
• Extra space during initialization of succinct data structures and dynamical initializable arrays
• Frameworks for designing in-place graph algorithms
• Planar Maximum Matching: Towards a Parallel Algorithm
• Space-efficient graph kernelizations
• Space-efficient biconnected components and recognition of outerplanar graphs

This page was built for publication: Space-efficient approximation scheme for maximum matching in sparse graphs

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