Finding Minimal Clusters in st-DAGs

Read full text Summarise with VIRAT
Authors: Ulrich Vogl, Markus Siegle
Cited by: 0
References: 16

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Directed Acylic Graphs with a single entry vertex and a single exit vertex (st-DAGs) have many applications. For instance, they are frequently used for modelling flow problems or precedence conditions among tasks, work packages, etc.. This paper presents an algorithm for finding special types of subgraphs in such st-DAGs, called clusters. Knowing the clusters of a given st-DAG is very useful during DAG analysis. Clusters are characterized by a kind of synchronizing behaviour at their entry border and at their exit border. In this context, we introduce the notion of syncpoint, a type of synchronisation point within a DAG, and for a given st-DAG we construct a second DAG, called MSP-DAG, whose edges are given by the precedence relation among maximum size syncpoints (MSPs). Our new cluster finding algorithm searches for clusters between potential pairs of enclosing MSPs. The efficiency of the algorithm stems from the fact that it works on the MSP-DAG, which is usually much smaller than the original st-DAG. The paper includes a thorough complexity analysis of the algorithm's runtime, which turns out to be quadratic in the number of DAG vertices and exponential in the number of MSP-DAG vertices. There is also a section reporting on experiments with randomly generated DAGs, which shows the practical applicability of the algorithm and confirm our theoretical findings.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Graph Theory and Algorithms

Publication details

Journal / source
arXiv (Cornell University)
Publication date
27 March 2026
Language
EN
Document type
Preprint