Finding Minimal Clusters in st-DAGs
Ulrich Vogl, Markus Siegle · 2026
Read Finding Minimal Clusters in st-DAGs by Ulrich Vogl, Markus Siegle (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26538.txt.
Description
Vogl and Siegle present an algorithm for finding minimal clusters in st-DAGs, graphs with one entry and one exit vertex. Such graphs model flows and task precedence in many fields. Clusters are subgraphs with a syncing trait at their entry and exit borders. The authors define syncpoints, then build a smaller graph from the largest ones. Their search runs on that smaller graph, which keeps it fast in practice. Runtime is quadratic in the main graph's vertices, and tests use random graphs.
Catalog record
| CREATOR | Ulrich Vogl, Markus Siegle |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60621 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.26538