Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs

DOI10.4230/LIPIcs.MFCS.2016.28zbMath1398.05163OpenAlexW2543489815MaRDI QIDQ4608587

Anish Mukherjee, Samir Datta, Raghav Kulkarni

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 graphsmaximum matchingapproximation schemelogspace

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)

Related Items (5)

Space-efficient biconnected components and recognition of outerplanar graphs ⋮ 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 ⋮ Simple 2^f-Color Choice Dictionaries

This page was built for publication: Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs