Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871106 | Discrete Applied Mathematics | 2018 | 12 Pages |
Abstract
A flowgraph G=(V,A,s) is a digraph such that there is a dipath from s to u for every vertex u in G. A vertex w dominates a vertex u if and only if all dipaths in G from s to u pass through w. The vertex s dominates trivially any vertex in G. In this work, we define two sets called dominator cover and junction partition. A dominator cover in G is a set of vertices that includes s and non-trivial dominators for all vertices in G. A junction partition B={B1,â¦,Bk} is a partition of V which satisfies the following property: if vertex u belongs to Bi and vertex v belongs to Bj (iâ j), then there are internally vertex-disjoint dipaths from s to u and from s to v, for short, s is a junction of u and v. The first part of this work shows that, in flowgraphs, the minimum size of a dominator cover is equal to the maximum size of a junction partition. The second part describes some applications for this relation, such as, a new correctness proof of an algorithm that finds a maximum junction partition in reducible flowgraphs; and good time and space complexity algorithms for problems related to junctions and nearest common ancestors in acyclic digraphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Carlos Eduardo Ferreira, Álvaro Junio Pereira Franco,