Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.97
URN: urn:nbn:de:0030-drops-91011
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9101/
Sankowski, Piotr
NC Algorithms for Weighted Planar Perfect Matching and Related Problems
| pdf-format: |
|
Abstract
Consider a planar graph G=(V,E) with polynomially bounded edge weight function w:E -> [0, poly(n)]. The main results of this paper are NC algorithms for finding minimum weight perfect matching in G. In order to solve this problems we develop a new relatively simple but versatile framework that is combinatorial in spirit. It handles the combinatorial structure of matchings directly and needs to only know weights of appropriately defined matchings from algebraic subroutines.Moreover, using novel planarity preserving reductions, we show how to find: maximum weight matching in G when G is bipartite; maximum multiple-source multiple-sink flow in G where c:E -> [1, poly(n)] is a polynomially bounded edge capacity function; minimum weight f-factor in G where f:V -> [1, poly(n)]; min-cost flow in G where c:E -> [1, poly(n)] is a polynomially bounded edge capacity function and b:V -> [1, poly(n)] is a polynomially bounded vertex demand function. There have been no known NC algorithms for these problems previously.
BibTeX - Entry
@InProceedings{sankowski:LIPIcs:2018:9101,
author = {Piotr Sankowski},
title = {{NC Algorithms for Weighted Planar Perfect Matching and Related Problems}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {97:1--97:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9101},
URN = {urn:nbn:de:0030-drops-91011},
doi = {10.4230/LIPIcs.ICALP.2018.97},
annote = {Keywords: planar graph, NC algorithms, maximum cardinality matching, maximum weight matching, min-cost flow, maximum multiple-source multiple-sink flow, f-facto}
}
| Keywords: | planar graph, NC algorithms, maximum cardinality matching, maximum weight matching, min-cost flow, maximum multiple-source multiple-sink flow, f-facto | |
| Seminar: | 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 04.07.2018 |
