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

DOI10.4230/LIPICS.ESA.2017.8MaRDI QIDQ5111691zbMATH OpenFDO

Authors Daniel Antunes, Claire Mathieu, Nabil H. Mustafa

Publication date 27 May 2020

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)

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

Cites work

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

Cited in

(4)

• Optimality of geometric local search
• A tight analysis 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)