-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
158 lines (127 loc) · 11.4 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Design by Free CSS Templates
http://www.freecsstemplates.org
Released for free under a Creative Commons Attribution 2.5 License
Name : Old Stairwell
Description: A two-column, fixed-width design with dark color scheme.
Version : 1.0
Released : 20130313
-->
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="google-site-verification" content="TKhkDFKyhvcrubOqVQVf7xQG4bUSzAuJlXiN4_Ts7yQ" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Vienna Minimum Cuts </title>
<meta name="keywords" content="graph partitioning, multilevel algorithm, minimum cut, minimum cuts, viecut, open source, kahip, algorithm, software, shared-memory parallel, parallel, label propagation, max flow, min cut" />
<meta name="description" content="The main project page of to open source framework VieCut -- Vienna Minimum Cuts" />
<link rel="shortcut icon" type="image/x-icon" href="favicon.ico">
<link href="http://fonts.googleapis.com/css?family=Open+Sans:400,300,600,700" rel="stylesheet" type="text/css">
<link href="default.css" rel="stylesheet" type="text/css" media="all" />
<!--[if IE 6]>
<link href="default_ie6.css" rel="stylesheet" type="text/css" />
<![endif]-->
</head>
<body>
<div id="wrapper">
<div id="header">
<div id="logo">
<h1><a href="#">VieCut - </a><a href="#" style="color:red">Vie</a><a href="#">nna </a> <a href="#">Minimum</a> <a href="#" style="color:red">Cut</a><a href="#">s</a> </h1>
Monika Henzinger, Alexander Noe, Christian Schulz and Darren Strash
</div>
</div>
<div id="page">
<div id="content">
<h2>Overview</h2>
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. It is a fundamental graph problem with many applications in different fields, such as network reliability, where assuming equal failure probability edges, the smallest edge cut in the network has the highest chance to disconnect the network; in VLSI design, where the minimum cut can be used to minimize the number of connections between microprocessor blocks; and as a subproblem in branch-and-cut algorithms for the Traveling Salesman Problem (TSP) and other combinatorial problems.
<br>
<br>
VieCut - <a href="#" style="color:red">Vie</a>nna Minimum <a href="#" style="color:red">Cut</a>s -- is a shared-memory parallel heuristic algorithm for the minimum cut problem. Based on the algorithm we also present a fast and exact shared-memory parallel algorithm for the minimum cut problem.
We provide it here as easy to use open source software.
The algorithm is based on the label propagation algorithm, the contraction tests of Padberg and Rinaldi and the minimum cut algorithm of Nagamochi et al. and computes minimum cuts of huge networks fast and with use of shared-memory parallelism. While VieCut can not guarantee solution quality, in practice the algorithm outputs better cuts than other inexact algorithms in significantly lower time, especially when using shared-memory parallelism. This codebase also includes a fast and exact shared-memory parallel based on VieCut and the algorithm of Nagamochi et al. Using the high-quality cuts given by VieCut the algorithm can detect and contract contractible edges fast and in parallel. Using these techniques we can compute exact minimum cuts significantly faster than the state of the art, sometimes with speedups of more than an order of magnitude.
<br><br>
Additionally we give a branch-and-reduce algorithm for the multiterminal cut problem.
The multiterminal cut problem is the NP-hard generalization of the minimum s-t-cut problem to more than two terminal vertices.
Our algorithm combines a multitude of kernelization routines with a sophisticated branching routine and is able to solve this problem on some very large instances.
Even if the algorithm is not able to guarantee optimality of its solution in a problem, it gives a high-quality approximation.
<br><br>
<b style="color:red">News:</b> <br>
<b> 13th December 2019:</b> Published instances used for paper Shared-Memory Branch-and-Reduce for Multiterminal Cuts. Please see Downloads below.<br>
<b> 12th August 2019:</b> Published ArXiv Report (Shared-Memory Branch-and-Reduce for Multiterminal Cuts). Link to <a href="https://arxiv.org/abs/1908.04141">PDF</a>.<br>
<b> 21st May 2019:</b> We presented our paper "Shared-memory Exact Minimum Cuts" at IPDPS 2019 <br>
<b> 7th January 2019:</b> Released VieCut v1.00. <br>
<b>16th August 2018:</b> Published ArXiv Report (Shared-memory Exact Minimum Cuts). Link to <a href="https://arxiv.org/abs/1808.05458">PDF</a>.<br>
<b> 7th January 2018</b> We presented our paper "Practical Minimum Cut Algorithms" at ALENEX 2018 <br>
<b>27th August 2017:</b> Published ArXiv Report (Practical Minimum Cut Algorithms). Link to <a href="https://arxiv.org/abs/1708.06127">PDF</a>.<br>
<p></p>
<br>
<h2>License</h2>
The program is licenced under the MIT license.<br>
If you publish results using our algorithms, <b>please acknowledge</b> our work by referencing all applicable papers:<br><br>
<b>@article{Henzinger2018Practical, <br>
             AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian and Strash, Darren},<br>
             TITLE = {{Practical Minimum Cut Algorithms}},<br>
             JOURNAL={Journal of Experimental Algorithmics (JEA)}, <br>
<!--             VOLUME = {75},<br>-->
             VOLUME={23},<br>
             NUMBER={1},<br>
             PAGES={1--8},<br>
             YEAR = {2018},<br>
             PUBLISHER={ACM},<br>
}</b>
<br><br>
<b>@inproceedings{henzinger2019shared, <br>
             AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},<br>
             TITLE = {{Shared-memory Exact Minimum Cuts}},<br>
             BOOKTITLE = {2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)},<br>
             PAGES = {13--22},<br>
             ORGANIZATION = {IEEE},<br>
             YEAR = {2019}<br>
}</b>
<br><br>
<b>@inproceedings{henzinger2019branch, <br>
             AUTHOR = {Henzinger, Monika and Noe, Alexander and Schulz, Christian},<br>
             TITLE = {{Shared-memory Branch-and-Reduce for Multiterminal Cuts}},<br>
             JOURNAL = {arXiv preprint arXiv:1908.04141},<br>
<!--             VOLUME = {75},<br>-->
             YEAR = {2019}<br>
}</b>
<br><br>
The algorithms that are included for download are mainly based on the following publications: <br> <br>
<ul>
<li> Monika Henzinger, Alexander Noe, Christian Schulz and Darren Strash. Practical Minimum Cut Algorithms. Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX'18). 2018. <a href="https://arxiv.org/abs/1708.06127">Download PDF</a>.<br>
<li> Monika Henzinger, Alexander Noe and Christian Schulz. Shared-memory Exact Minimum Cuts. 2019. 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS) <a href="http://arxiv.org/pdf/1808.05458.pdf">Download PDF</a>.<br>
<li> Monika Henzinger, Alexander Noe and Christian Schulz. Shared-memory Branch-and-Reduce for Multiterminal Cuts. 2019. (to appear at ALENEX'20) <a href="http://arxiv.org/pdf/1908.04141.pdf">Download PDF</a>.<br><br>
</ul>
<p></p>
<h2>Download</h2>
<ul>
<li> Code and user guide available on GitHub <a href="https://github.com/VieCut/VieCut/">here</a>
<li> <a href="http://viecut.taa.univie.ac.at/viecutv1_00.tar.gz">viecutv1_00.tar.gz</a> (submodules accessed on 7. January 2019)
<li> Instances used for multiterminal cut problem: <a href="http://viecut.taa.univie.ac.at/instances.tar.gz">instances.tar.gz</a>
</ul>
<h2>Support</h2>
<ul>
<li> Write us an <a href="mailto:[email protected]?subject=SupportRequestVieCut">email</a> if you need support!
<li>We are glad for any comments and error reports (or even bug fixes or feature requests) that you send us.
</ul>
<h2>Other Open Source Projects</h2>
<ul>
<li> <a href="http://algo2.iti.kit.edu/kahip">KaHIP</a> -- Karlsruhe High Quality Partitioning
<li> <a href="http://algo2.iti.kit.edu/kahip">ParHIP</a> -- Parallel High Quality Partitioning
<li> <a href="http://algo2.iti.kit.edu/kamis">KaMIS</a> -- Karlsruhe Maximum Independent Sets
<li> <a href="http://algo2.iti.kit.edu/kalp">KaLP</a> -- Karlsruhe Longest Paths
<li> <a href="http://algo2.iti.kit.edu/kadraw">KaDraw</a> -- Karlsruhe Graph Drawing
<li> <a href="http://viem.taa.univie.ac.at">VieM</a> -- Vienna Mapping and Sparse Quadratic Assignment
<li> <a href="http://vieclus.taa.univie.ac.at">VieClus</a> -- Vienna Graph Clustering
</ul>
</a>
</div>
</div>
<div id="footer">
<p>Copyright (c) 2018-2020. Site maintained by Alexander Noe. All rights reserved. Initial release of VieCut: 7. January 2019. See main site for impressum. Design by <a href="http://www.freecsstemplates.org">FCT</a>.</p>
</div>
</div>
</body>
</html>