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

approximation schemelogspacemaximum matchingplanar graphs

Mathematics Subject Classification ID

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

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

(9)

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

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)