Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:48:25Z
dc.abstract.enConsider 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryCzechy
dc.conference.datefinish2018-07-13
dc.conference.datestart2018-07-09
dc.conference.placePraha
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2018
dc.conference.weblinkhttps://iuuk.mff.cuni.cz/events/icalp2018/
dc.contributor.authorSankowski, Piotr
dc.date.accessioned2024-01-25T13:31:22Z
dc.date.available2024-01-25T13:31:22Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.identifier.doi10.4230/LIPICS.ICALP.2018.97
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/113449
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2018/9101/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages97:1-97:16
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enplanar graph
dc.subject.enNC algorithms
dc.subject.enmaximum cardinality matching
dc.subject.enmaximum weight matching
dc.subject.enmin-cost flow
dc.subject.enmaximum multiple-source multiple-sink flow
dc.subject.enf-facto
dc.titleNC Algorithms for Weighted Planar Perfect Matching and Related Problems
dc.typeJournalArticle
dspace.entity.typePublication