Paper Info
Title
Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs.
Abstract
Local search for combinatorial optimization problems is becoming a dominant algorithmic paradigm, with several papers using it to resolve long-standing open problems. In this paper, we prove the following `4-localu0027 version of Hallu0027s theorem for planar graphs: given a bipartite planar graph G = (B, R, E) such that |N(Bu0027)| u003e= |Bu0027| for all |Bu0027| u003c= 4, there exists a matching of size at least |B|/4 in G; furthermore this bound is tight. Besides immediately implying improved bounds for several problems studied in previous papers, we find this variant of Hallu0027s theorem to be of independent interest in graph theory.
Year
Venue
Field
2017
ESA
Graph theory,Discrete mathematics,Combinatorics,Hall's marriage theorem,Dilworth's theorem,Bipartite graph,Steinitz's theorem,Bruck–Ryser–Chowla theorem,Mirsky's theorem,Planar graph,Mathematics
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Daniel Antunes100.34
Claire Mathieu245225.78
Nabil H. Mustafa339041.24