Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs

DOI10.4230/LIPICS.ESA.2017.8zbMATH Open1442.05041MaRDI QIDQ5111691FDOQ5111691

Authors: Daniel Antunes, Claire Mathieu, Nabil H. Mustafa 

Publication date: 27 May 2020

Recommendations

• Hall's theorem revisited
• Independent transversals and hypergraph matchings -- an elementary approach
• A generalization of Hall's theorem for \(k\)-uniform \(k\)-partite hypergraphs
• Perfect matchings in balanced hypergraphs---a combinatorial approach

zbMATH Keywords

combinatorial optimizationlocal searchexpansionplanar graphsHall's theorem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• Geometric hitting sets for disks: theory and practice
• Improved results on geometric hitting set problems
• The discharging method in combinatorial geometry and the Pach-Sharir conjecture
• Independent set of intersection graphs of convex objects in 2D
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Algorithms – ESA 2005
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation algorithms for maximum independent set of pseudo-disks
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Simple PTAS's for families of graphs excluding a minor
• Guarding terrains via local search
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Packing and covering with non-piercing regions
• Approximation Schemes for Covering and Packing
• Limits of local search: quality and efficiency

Cited In (4)

• A tight analysis of geometric local search
• Optimality of geometric local search
• Constructing planar support for non-piercing regions
• Local search is a PTAS for feedback vertex set in minor-free graphs

This page was built for publication: Combinatorics of local search: an optimal 4-local Hall's theorem for planar graphs

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