Covering Directed Graphs by In-trees

Details Covering Directed Graphs by In-trees Covering Directed Graphs by In-trees

2008-02-20

arxiv.org/abs/0802.2755v1

Computer Science

Discrete Mathematics

15 pages, 12 figures

Scientific paper

Given a directed graph $D=(V,A)$ with a set of $d$ specified vertices $S=\{s_1,...,s_d\}\subseteq V$ and a function $f\colon S \to \mathbb{Z}_+$ where $\mathbb{Z}_+$ denotes the set of non-negative integers, we consider the problem which asks whether there exist $\sum_{i=1}^d f(s_i)$ in-trees denoted by $T_{i,1},T_{i,2},..., T_{i,f(s_i)}$ for every $i=1,...,d$ such that $T_{i,1},...,T_{i,f(s_i)}$ are rooted at $s_i$, each $T_{i,j}$ spans vertices from which $s_i$ is reachable and the union of all arc sets of $T_{i,j}$ for $i=1,...,d$ and $j=1,...,f(s_i)$ covers $A$. In this paper, we prove that such set of in-trees covering $A$ can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in $\sum_{i=1}^df(s_i)$ and the size of $D$. Furthermore, for the case where $D$ is acyclic, we present another characterization of the existence of in-trees covering $A$, and then we prove that in-trees covering $A$ can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs.

Affiliated with

Also associated with

No associations

Rating

Covering Directed Graphs by In-trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Covering Directed Graphs by In-trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Covering Directed Graphs by In-trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647053