Busca avançada
Ano de início
Entree


A min-max relation in flowgraphs and some applications

Texto completo
Autor(es):
Ferreira, Carlos Eduardo ; Pereira Franco, Alvaro Junio
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: DISCRETE APPLIED MATHEMATICS; v. 245, p. 12-pg., 2018-08-20.
Resumo

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 = {B-1, . . . , B-k) is a partition of V which satisfies the following property: if vertex u belongs to B-j and vertex v belongs to B-j (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. (C) 2017 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Modalidade de apoio: Auxílio à Pesquisa - Temático