Generalized planar matching

DOI10.1016/0196-6774(90)90001-UMaRDI QIDQ3357535zbMATH OpenOpenAlexFDO

Authors Fran Berman, Tom Leighton, Larry Snyder, D. S. Johnson, Peter W. Shor

Publication date 1990

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(90)90001-u

zbMATH Keywords

approximation algorithmmatchingplanar graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3965443
• Approximation algorithms for NP-complete problems on planar graphs
• Algorithms – ESA 2004
• Maximum matchings in planar graphs via Gaussian elimination
• Maximum bounded \(H\)-matching is Max SNP-complete

Cited in

(30)

• Paarweise kantendisjunkte maximale matchings in normalen periodischen Pflasterungen. (On pairwise edge-disjoint maximal matchings in normal periodic tilings)
• Forests, colorings and acyclic orientations of the square lattice
• Maximum bounded \(H\)-matching is Max SNP-complete
• Tiling figures of the plane with two bars
• Maximum tree-packing in time \(O(n^{5/2})\)
• Tile invariants: New horizons.
• Illuminating disjoint line segments in the plane
• Winner determination in geometrical combinatorial auctions
• Maximum packing for biconnected outerplanar graphs
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Revising Johnson's table for the 21st century
• Simplified group activity selection with group size constraints
• A Survey of the Game “Lights Out!”
• Planarizing Gadgets for Perfect Matching Do Not Exist
• Network-based dissolution
• Matching planar maps
• Combinatorial and computational aspects of graph packing and graph decomposition
• Planarizing gadgets for perfect matching do not exist
• Network-based vertex dissolution
• Tiling with Squares and Packing Dominos in Polynomial Time
• Maximum tree-packing in time O(n5/2)
• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes
• Approximation algorithms for non-sequential star packing problems
• On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes
• Partitioning vertices of graphs into paths of the same length
• Approximation algorithms for the k^+-star packing problem
• Approximation algorithms for non-sequential star packing problems
• Induced packing of odd cycles in planar graphs
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs

This page was built for publication: Generalized planar matching

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