Zobrazeno 1 - 10
of 31
pro vyhledávání: '"Noe, Alexander"'
Autor:
Dong, Yuanyuan, Goldberg, Andrew V., Noe, Alexander, Parotsidis, Nikos, Resende, Mauricio G. C., Spaen, Quico
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs ai
Externí odkaz:
http://arxiv.org/abs/2203.15805
Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice?
Autor:
Henzinger, Monika, Noe, Alexander
Fully dynamic graph algorithms that achieve polylogarithmic or better time per operation use either a hierarchical graph decomposition or random-rank based approach. There are so far two graph properties for which efficient algorithms for both types
Externí odkaz:
http://arxiv.org/abs/2108.04564
Autor:
Noe, Alexander
Graphs are a natural representation of data from various contexts, such as social connections, the web, road networks, and many more. In the last decades, many of these networks have become enormous, requiring efficient algorithms to cut networks int
Externí odkaz:
http://arxiv.org/abs/2108.04566
Autor:
Dong, Yuanyuan, Goldberg, Andrew V., Noe, Alexander, Parotsidis, Nikos, Resende, Mauricio G. C., Spaen, Quico
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve in part because of their large size. We present instances with up to 8
Externí odkaz:
http://arxiv.org/abs/2105.12623
We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a
Externí odkaz:
http://arxiv.org/abs/2101.05033
Autor:
Abu-Khzam, Faisal, Lamm, Sebastian, Mnich, Matthias, Noe, Alexander, Schulz, Christian, Strash, Darren
Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has resulted in an algorithmic toolbox that is by now well-established. Howev
Externí odkaz:
http://arxiv.org/abs/2012.12594
We give an improved branch-and-bound solver for the multiterminal cut problem, based on the recent work of Henzinger et al.. We contribute new, highly effective data reduction rules to transform the graph into a smaller equivalent instance. In additi
Externí odkaz:
http://arxiv.org/abs/2004.11666
We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using
Externí odkaz:
http://arxiv.org/abs/2002.06948
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We introduce the fastest known exact algorithm~for~the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the perform
Externí odkaz:
http://arxiv.org/abs/1908.04141