1 Search Results for "Vinodchandran, N. Variyam"

Document
DOI: 10.4230/LIPIcs.STACS.2011.579
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

Authors: Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. Variyam Vinodchandran

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that the problems of deciding whether such graphs have (1) a perfect matching or not and (2) a unique perfect matching or not, are in the logspace complexity class SPL. Since SPL is contained in the logspace counting classes oplus L (in fact in mod_k for all k >= 2), C=L, and PL, our upper bound places the above-mentioned matching problems in these counting classes as well. We also show that the search version, computing a perfect matching, for this class of graphs is in FL^SPL. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a logspace computable and polynomially bounded weight function which isolates a minimum weight perfect matching in bipartite graphs embedded on surfaces of constant genus. We use results from algebraic topology for proving the correctness of the weight function.
Cite as

Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. Variyam Vinodchandran. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 579-590, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2011.579,
  author =	{Datta, Samir and Kulkarni, Raghav and Tewari, Raghunath and Vinodchandran, N. Variyam},
  title =	{{Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{579--590},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.579},
  URN =		{urn:nbn:de:0030-drops-30450},
  doi =		{10.4230/LIPIcs.STACS.2011.579},
  annote =	{Keywords: perfect matching, bounded genus graphs, isolation problem}
}
  • Refine by Author
  • 1 Datta, Samir
  • 1 Kulkarni, Raghav
  • 1 Tewari, Raghunath
  • 1 Vinodchandran, N. Variyam

  • Refine by Classification

  • Refine by Keyword
  • 1 bounded genus graphs
  • 1 isolation problem
  • 1 perfect matching

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2011

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