Zobrazeno 1 - 10
of 110
pro vyhledávání: '"Harold N. Gabow"'
Autor:
Harold N. Gabow, Piotr Sankowski
Publikováno v:
SIAM Journal on Computing
For an undirected graph or multigraph $G=(V,E)$ and a function $f:V\to \mathbb{Z_+}$, an $f$-factor is a subgraph whose degree function is $f$. For integral edge weights of maximum magnitude $W$ ou...
Autor:
Piotr Sankowski, Harold N. Gabow
Publikováno v:
SIAM Journal on Computing
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$-m...
Autor:
Harold N. Gabow
Blocking flows, introduced by Dinic [2] for network flow, have been used to speed up many augmenting-path type algorithms, especially matching algorithms e.g., [18, 23, 16]. We present an $O(m)$ time algorithm for blocking trails for f-factors of gen
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7c57120abb50e3321cf67b587ec9a36a
Autor:
Harold N. Gabow
Publikováno v:
ACM Transactions on Algorithms. 13:1-28
Consider a forest that evolves via $link$ operations that make the root of one tree the child of a node in another tree. Intermixed with $link$ operations are $nca$ operations, which return the nearest common ancestor of two given nodes when such exi
Autor:
Harold N. Gabow
Publikováno v:
ACM Transactions on Algorithms. 12:1-73
Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all st -minimum cuts of a flow network. We begin with an explanation of why this poset stru
Publikováno v:
53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012
Consider a directed or an undirected graph with integral edge weights from the set [-W, W], that does not contain negative weight cycles. In this article, we introduce a general framework for solving problems on such graphs using matrix multiplicatio
Autor:
Harold N. Gabow
Several papers have achieved time $O(\sqrt n m)$ for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds' algorithm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5a1df625e1779c5b929e9e85df2ef6e8
Autor:
Harold N. Gabow
This paper shows the weighted matching problem on general graphs can be solved in time $O(n(m + n\log n))$ for $n$ and $m$ the number of vertices and edges, respectively. This was previously known only for bipartite graphs. The crux is a data structu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ee9aeb6806eeb427c8b654cc6c62a509
Publikováno v:
Networks. 53:345-357