An algorithm for optimum common root functions of two digraphs

✍ Scribed by Mao-cheng Cai

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 427 KB
• Volume: 119
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90114-9

✦ Synopsis

An algorithm for optimum common root functions of two digraphs, Discrete -i? Mathematics 119 (1993) 13-20. ,%I, Let G1 and G, be finite digr,phs, both with vertex set V. Suppose that each c of V has nonnegative integers f(a) and g(u) with,'f(o)<g( ). v and each arc e of G, has nonnegative integers a;(e) and h;(e) with ai(e)<hi(e), i= 1,2. In dai (1990) a necessary and sufficient condition was given for the existence of k arborescences in Gi covering each arc e of Gi at least q(e) and at most hi(e) times, i= 1,2, and satisfying the condition that for each v in V where ri(v) denotes the number of the arborescences in G, rooted at c'. Such an r, is called a common root function and denoted by r.

In this paper, we present a polynomial algorithm for finding an optimum common root function r for a given weight function defined on V.

Let G = (P', A) be a finite digraph with vertex set V and arc set A and without loops. We write S= V\S for Ss V and V\v= V{u} f or UEV. An arc from vertex u to u is denoted by uu. For disjoint S, TG V, let A(& T) denote the set of arcs of G from S to T, D;(S)=A(S,S), d;(S)=ID;(S)l, D~(S)=D;(~) and dG+(S)=IDG+(S)I. An arhorescence of G is defined as a spanning tree directed in such a way that each vertex of G, except one, called the root of the arborescence, has one arc entering it. We say that an arc subset B of G =( V, A) is covered by arborescences T1, . . . , T, if every arc of B is in at least one Ti.