Jan Heuvel van den
Transversals of subtree hypergraphs and the source location problem in hypergraphs
Heuvel van den, Jan; Johnson, M.
Authors
M. Johnson
Abstract
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.
Citation
Heuvel van den, J., & Johnson, M. (2004). Transversals of subtree hypergraphs and the source location problem in hypergraphs. [No known commissioning body]
Report Type | Technical Report |
---|---|
Publication Date | 2004-05 |
Deposit Date | Apr 24, 2008 |
Publicly Available Date | Apr 24, 2008 |
Keywords | Graphs, Hypergraphs, Source location, Algorithms. |
Publisher URL | http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-10.pdf |
Additional Information | Additional Information: CDAM Research Reports Series. Department Name: Centre for Discrete and Applicable Mathematics University Name: London School of Economics Publisher: London School of Economics Type: monograph Subtype: technical_report |
Files
Published Report
(190 Kb)
PDF
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search