|
Recently Bárász, Becker and Frank gave a strongly polynomial time algorithm that solves the Directed Source Location Problem, which is the following: given a D=(V,A) directed graph and positive integers k and l, find the minimum cardinality set R \subseteq V such that contracting R into a single node r in the graph D results in graph which is (k,l)-edge-connected with respect to the root node r. They introduce the notion of solid sets and observe that the union of two intersecting solid sets is also solid. The bottleneck operation of their algorithm is the step of determining the hypergraph H = { X: X is a maximal s-avoiding solid set for some s \in V }. It is easy to see that H has at most n(n-1) elements: the motivation of the present work was to prove that one can give a better bound on |H|. Namely we prove here that |H| \le 2(n-1).
Bibtex entry:
| AUTHOR | = | {Bern{\'a}th, Attila}, |
| TITLE | = | {A note on the directed source location algorithm}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2004}, |
| NUMBER | = | {TR-2004-12} |