Zobrazeno 1 - 10
of 427
pro vyhledávání: '"Gabow P"'
Autor:
Gabow, Harold
We present an algorithm that finds a maximum cardinality $f$-matching of a simple graph in time $O(n^{2/3} m)$. Here $f:V\to \mathbb{N}$ is a given function, and an $f$-matching is a subgraph wherein each vertex $v\in V$ has degree $\le f(v)$. This r
Externí odkaz:
http://arxiv.org/abs/2311.14236
Publikováno v:
Risk Management and Healthcare Policy, Vol Volume 17, Pp 2573-2585 (2024)
Nur Adam Mohamed,1 Yusuf Abdirisak Mohamed,1,2 Tigad Abdisad Ali,3 Adan Ali Gabow,1 Fartun Mohamed Hilowle4 1Mogadishu Somali Turkiye Recep Tayyip Erdogan Training and Research Hospital, Department of Psychiatry and Behavioral Sciences, Mogadishu, So
Externí odkaz:
https://doaj.org/article/127986763a0c4a03b2d7f369a0da26f2
Autor:
Gabow, Harold N.
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:
http://arxiv.org/abs/2112.04096
Autor:
Gabow, Harold
We discuss combinatorial algorithms for finding a maximum weight $f$-factor on an arbitrary multigraph, for given integral weights of magnitude at most $W$. For simple bipartite graphs the best-known time bound is $O(n^{2/3}\, m\, \log nW)$ (\cite{GT
Externí odkaz:
http://arxiv.org/abs/2010.01102
Autor:
Gabow, Harold N.
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:
http://arxiv.org/abs/1703.03998
Autor:
Gabow, Harold N.
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:
http://arxiv.org/abs/1611.07541
Autor:
Gabow, Harold N.
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
Externí odkaz:
http://arxiv.org/abs/1611.07055
Autor:
Gabow, Harold N.
The algorithm of Micali and Vazirani \cite{MV} finds a maximum cardinality matching in time $O(\sqrt n m)$ if an efficient set-merging algorithm is used. The latter is provided by the incremental-tree set-merging algorithm of \cite{GabTar}. Details o
Externí odkaz:
http://arxiv.org/abs/1501.00212
Autor:
Gabow, Harold N., Sankowski, Piotr
Let G=(V,E) be a graph with f:V\to Z_+ a function assigning degree bounds to vertices. We present the first efficient algebraic algorithm to find an f-factor. The time is \tilde{O}(f(V)^{\omega}). More generally for graphs with integral edge weights
Externí odkaz:
http://arxiv.org/abs/1304.6740
We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job has an integer length as well as a set Ti of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can sc
Externí odkaz:
http://arxiv.org/abs/1208.0312