Space-efficient approximation scheme for maximum matching in sparse graphs

DOI10.4230/LIPICS.MFCS.2016.28MaRDI QIDQ4608587zbMATH OpenOpenAlexFDO

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/

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)

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

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)