Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Matthew Johnson

Heuvel van den, Jan & Johnson, M. (2008). Transversals of subtree hypergraphs and the source location problem in digraphs. Networks 51(2): 113-119.

Author(s) from Durham

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 ⊆ V is a transversal in time S(n) (where n = |V|), then it is possible to find a minimum size transversal in O(n3S(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 ∈ 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.

References

1

K. Arata, S. Iwata, K. Makino, and S. Fujishige, Locating sources to meet flow demands
in undirected networks. J. of Algorithms, 42 (2002), 54–68.

2

M. B´ar´asz, J. Becker and A. Frank, An algorithm for source location in directed graphs.
Preprint (2004).

3

R. Diestel, Graph Theory. Springer-Verlag, New York (1997).

4

P. Duchet, Hypergraphs. In : R. Graham, M. Gr¨otschel, and L. Lov´asz, eds., Handbooks
of Combinatorics, Elsevier Science B.V. (1995), 381–432.

5

J. Hao and J. B. Orlin, A faster algorithm for finding the minimum cut in a graph. J. of
Algorithms, 17 (1994), 424–446.

6

H. Ito, M. Ito, Y. Itatsu, K. Nakai, H. Uehara, and M. Yokoyama, Source Location Problems
considering vertex-connectivity and edge-connectivity simultaneously. Networks, 40
(2002), 63–70.

7

H. Ito, M. Ito, Y. Itatsu, H. Uehara, and M. Yokohama, Location problems based on
node-connectivity and edge-connectivity between nodes and node-subsets. Lecture Notes
in Computer Science, 1969 (2000), 338–349.

8

H. Ito, K. Makino, K. Arata, S. Honami, Y. Itatsu, and S. Fujishige, Source location
problem with flow requirements in directed networks. Optimization Methods and Software,
18 (2003), 427–435.

9

H. Ito, H. Uehara, and M., Yokoyama, A faster and flexible algorithm for a location
problem on undirected flow networks. IEICE Trans., E83-A (2000), 704–712.

10

H. Ito and M. Yokoyama, Edge-connectivity between nodes and node-subsets, Networks,
31 (1998), 157–164.

11

M. Labbe, D. Peeters, and J.-F. Thisse, Location on networks. In : M.O. Ball, T.L. Magnanti,
C.L. Monma, and G.L. Nemhauser, eds., Handbooks in Operations Research and
Management Science, 8 : Network Routing, North-Holland (1995), 551–624.

12

H. Nagamochi, T. Ishii, and H. Ito, Minimum cost source location problem with vertexconnectivity
requirements in digraphs. Info Process Letters, 80 (2001), 287–294.

13

H. Tamura, M. Sengoku, S. Shinoda, and T. Abe, Location problems on undirected flow
networks. IEICE Trans., E73 (1990), 1989–1993.

14

Open Problems page of the Egerv´ary Research Group on Combinatorial Optimization,
http://www.cs.elte.hu/egres/, http://www.cs.elte.hu/egres/design/
mf problems.html.