Heuvel van den, J. and Johnson, M. (2004) 'Transversals of subtree hypergraphs and the source location problem in hypergraphs.', Technical Report. London School of Economics, London.
A hypergraph $H=(V,E)$ is a subtree hypergraph if there is a tree~$T$ on~$V$ such that each hyperedge of~$E$ induces a subtree of~$T$. Since the number of edges of a subtree hypergraph can be exponential in $n=|V|$, one can not always expect to be able to find a minimum size transversal in time polynomial in~$n$. In this paper, we show that if it is possible to decide if a set of vertices $W\subseteq V$ is a transversal in time~$S(n)$ (\,where $n=|V|$\,), then it is possible to find a minimum size transversal in~$O(n^3\,S(n))$. This result provides a polynomial algorithm for the Source Location Problem\,: a set of $(k,l)$-sources for a digraph $D=(V,A)$ is a subset~$S$ of~$V$ such that for any $v\in V$ there are~$k$ arc-disjoint paths that each join a vertex of~$S$ to~$v$ and~$l$ arc-disjoint paths that each join~$v$ to~$S$. The Source Location Problem is to find a minimum size set of $(k,l)$-sources. We show that this is a case of finding a transversal of a subtree hypergraph, and that in this case~$S(n)$ is polynomial.
|Item Type:||Monograph (Technical Report)|
|Additional Information:||CDAM Research Reports Series ; LSE-CDAM-2004-10|
|Keywords:||Graphs, Hypergraphs, Source location, Algorithms.|
|Full text:||(VoR) Version of Record|
Download PDF (187Kb)
|Publisher Web site:||http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-10.pdf|
|Record Created:||24 Apr 2008|
|Last Modified:||18 Oct 2010 14:46|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|