3 Search Results for "Arora, Anish"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.21
Planar Maximum Matching: Towards a Parallel Algorithm

Authors: Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity [P W Kastelyn, 1967; Vijay Vazirani, 1988; Meena Mahajan and Kasturi R. Varadarajan, 2000; Datta et al., 2010; Nima Anari and Vijay V. Vazirani, 2017]. However, corresponding results for maximum matchings have been elusive. We partly bridge this gap by proving: 1) An SPL upper bound for planar bipartite maximum matching search. 2) Planar maximum matching search reduces to planar maximum matching decision. 3) Planar maximum matching count reduces to planar bipartite maximum matching count and planar maximum matching decision. The first bound improves on the known [Thanh Minh Hoang, 2010] bound of L^{C_=L} and is adaptable to any special bipartite graph class with non-zero circulation such as bounded genus graphs, K_{3,3}-free graphs and K_5-free graphs. Our bounds and reductions non-trivially combine techniques like the Gallai-Edmonds decomposition [L. Lovász and M.D. Plummer, 1986], deterministic isolation [Datta et al., 2010; Samir Datta et al., 2012; Rahul Arora et al., 2016], and the recent breakthroughs in the parallel search for planar perfect matchings [Nima Anari and Vijay V. Vazirani, 2017; Piotr Sankowski, 2018].
Cite as

Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ISAAC.2018.21,
  author =	{Datta, Samir and Kulkarni, Raghav and Kumar, Ashish and Mukherjee, Anish},
  title =	{{Planar Maximum Matching: Towards a Parallel Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.21},
  URN =		{urn:nbn:de:0030-drops-99695},
  doi =		{10.4230/LIPIcs.ISAAC.2018.21},
  annote =	{Keywords: maximum matching, planar graphs, parallel complexity, reductions}
}
Document
DOI: 10.4230/DagSemRep.290
Self-Stabilization (Dagstuhl Seminar 00431)

Authors: Anish Arora, Joffroy Beauquier, Shlomi Dolev, Ted Herman, and Willem-Paul de Roever

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Anish Arora, Joffroy Beauquier, Shlomi Dolev, Ted Herman, and Willem-Paul de Roever. Self-Stabilization (Dagstuhl Seminar 00431). Dagstuhl Seminar Report 290, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{arora_et_al:DagSemRep.290,
  author =	{Arora, Anish and Beauquier, Joffroy and Dolev, Shlomi and Herman, Ted and de Roever, Willem-Paul},
  title =	{{Self-Stabilization (Dagstuhl Seminar 00431)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{290},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.290},
  URN =		{urn:nbn:de:0030-drops-151744},
  doi =		{10.4230/DagSemRep.290},
}
Document
DOI: 10.4230/DagSemRep.220
Self-Stabilization (Dagstuhl Seminar 98331)

Authors: Anish Arora, Shlomi Dolev, and Willem-Paul de Roever

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Anish Arora, Shlomi Dolev, and Willem-Paul de Roever. Self-Stabilization (Dagstuhl Seminar 98331). Dagstuhl Seminar Report 220, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{arora_et_al:DagSemRep.220,
  author =	{Arora, Anish and Dolev, Shlomi and de Roever, Willem-Paul},
  title =	{{Self-Stabilization (Dagstuhl Seminar 98331)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{220},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.220},
  URN =		{urn:nbn:de:0030-drops-151066},
  doi =		{10.4230/DagSemRep.220},
}
  • Refine by Author
  • 2 Arora, Anish
  • 2 Dolev, Shlomi
  • 2 de Roever, Willem-Paul
  • 1 Beauquier, Joffroy
  • 1 Datta, Samir
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Parallel algorithms

  • Refine by Keyword
  • 1 maximum matching
  • 1 parallel complexity
  • 1 planar graphs
  • 1 reductions

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 1998
  • 1 2000
  • 1 2018

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