Algorithms for Junctions in Acyclic Digraphs

Carlos Eduardo Ferreira () and Álvaro Junio Pereira Franco ()
Additional contact information
Carlos Eduardo Ferreira: Instituto de Matemática e Estatística
Álvaro Junio Pereira Franco: Instituto de Matemática e Estatística

A chapter in Facets of Combinatorial Optimization, 2013, pp 175-194 from Springer

Abstract: Abstract Given targets u and v in a digraph D, we say that a vertex s is a junction of u and v if there are in D internally vertex-disjoint directed paths from s to u and from s to v. In this paper, we show how to characterize junctions in acyclic digraphs. We also consider the following problem and derive an efficient algorithm to solve it. Given an acyclic digraph D, a vertex s in D and k pairs of targets {u 1,v 1},…,{u k ,v k }, determine the pairs of targets {u i ,v i } for which s is a junction. This problem arises in an application brought to our attention by an anthropologist. In this application the digraph represents the genealogy of an ethnic group in Brazilian Amazon region, and the pairs of targets are individuals that are married. We apply our algorithm to find all the junctions of k pairs of targets on those kinship networks. Experiments have shown that our algorithm had a good performance for the inputs considered. Some results are described in this paper.

Keywords: Rooted Tree; Common Vertex; Kinship Network; Internal Vertex; Lower Common Ancestor (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-38189-8_8

Ordering information: This item can be ordered from
http://www.springer.com/9783642381898

DOI: 10.1007/978-3-642-38189-8_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().