Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyAlgorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors
| dc.abstract.en | Let $G=(V,E)$ be a weighted graph or multigraph, with $f$ or $b$ a function assigning a nonnegative integer to each vertex. An $f$-factor is a subgraph whose degree function is $f$; a perfect $b$-matching is a $b$-factor in the graph formed from $G$ by adding an unlimited number of copies of each edge. This two-part paper culminates in an efficient algebraic algorithm to find a maximum $f$-factor, i.e., $f$-factor with maximum weight. Along the way it presents simpler special cases of interest. Part II presents the maximum $f$-factor algorithm and the special case of shortest paths in conservative undirected graphs (negative edges allowed). Part I presents these results: An algebraic algorithm for maximum $b$-matching, i.e., maximum weight $b$-matching. It is almost identical to its special case $b\equiv 1$, ordinary weighted matching. The time is $O(Wb(V)^{\omega})$ for $W$ the maximum magnitude of an edge weight, $b(V)=\sum_{v\in V} b(v)$, and $\omega<2.373$ the exponent of matrix multiplication. An algebraic algorithm to find an $f$-factor. The time is $O(f(V)^{\omega})$ for $f(V)=\sum_{v\in V} f(v)$. The specialization of the $f$-factor algorithm to bipartite graphs and its extension to maximum/minimum bipartite $f$-factors. This improves the known complexity bounds for vertex capacitated max-flow and min-cost max-flow on a subclass of graphs. Each algorithm is randomized and has two versions achieving the above time bound: For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Gabow, Harold N. |
| dc.contributor.author | Sankowski, Piotr |
| dc.date.accessioned | 2024-01-24T15:40:59Z |
| dc.date.available | 2024-01-24T15:40:59Z |
| dc.date.issued | 2021 |
| dc.description.finance | Środki finansowe przyznane na realizację projektu w zakresie badań naukowych lub prac rozwojowych |
| dc.description.number | 2 |
| dc.description.volume | 50 |
| dc.identifier.doi | 10.1137/16M1106195 |
| dc.identifier.issn | 0097-5397 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/100442 |
| dc.identifier.weblink | https://epubs.siam.org/doi/pdf/10.1137/16M1106195 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | SIAM Journal on Computing |
| dc.relation.pages | 440-486 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |