1 Search Results for "Antunes, Daniel"

Document
DOI: 10.4230/LIPIcs.ESA.2017.8
Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs

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

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

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-local' version of Hall's theorem for planar graphs: given a bipartite planar graph G = (B, R, E) such that |N(B')| >= |B'| for all |B'| <= 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 Hall's theorem to be of independent interest in graph theory.
Cite as

Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{antunes_et_al:LIPIcs.ESA.2017.8,
  author =	{Antunes, Daniel and Mathieu, Claire and Mustafa, Nabil H.},
  title =	{{Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.8},
  URN =		{urn:nbn:de:0030-drops-78293},
  doi =		{10.4230/LIPIcs.ESA.2017.8},
  annote =	{Keywords: Planar graphs, Local search, Hall's theorem, Combinatorial optimization, Expansion}
}
  • Refine by Author
  • 1 Antunes, Daniel
  • 1 Mathieu, Claire
  • 1 Mustafa, Nabil H.

  • Refine by Classification

  • Refine by Keyword
  • 1 Combinatorial optimization
  • 1 Expansion
  • 1 Hall's theorem
  • 1 Local search
  • 1 Planar graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact