Name
Abstract | ||
|---|---|---|
Given a system (V,f,r) on a finite set V consisting of a posi-modular function f: 2 V 驴驴 and a modulotone function r: 2 V 驴驴, we consider the problem of finding a minimum set R 驴 V such that f(X) 驴 r(X) for all X 驴 V 驴 R. The problem, called the transversal problem, was introduced by Sakashita et al. [6] as a natural generalization of the source location problem and external network problem with edge-connectivity requirements in undirected graphs and hypergraphs.By generalizing [8] for the source location problem, we show that the transversal problem can be solved by a simple greedy algorithm if r is 驴-monotone, where a modulotone function r is 驴-monotone if there exists a permutation 驴 of V such that the function $p_r: V \times 2^V \rightarrow \mathbb{R}$ associated with r satisfies p r (u,W) 驴 p r (v, W) for all W 驴 V and u,v 驴 V with 驴(u) 驴 驴(v). Here we show that any modulotone function r can be characterized by p r as r(X) = max {p r (v,W)|v 驴 X 驴 V 驴 W}.We also show the structural properties on the minimal deficient sets ${\cal W}$ for the transversal problem for 驴-monotone function r, i.e., there exists a basic tree T for ${\cal W}$ such that 驴(u) ≤ 驴(v) for all arcs (u,v) in T, which, as a corollary, gives an alternative proof for the correctness of the greedy algorithm for the source location problem.Furthermore, we show that a fractional version of the transversal problem can be solved by the algorithm similar to the one for the transversal problem. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-10631-6_49 | Discrete Mathematics, Algorithms and Applications |
Keywords | DocType | Volume |
posi-modular systems,transversal problem,p r,modulotone requirements,monotone function,posi-modular function,source location problem,external network problem,permutation constraints,modulotone function,finite set v,cal w,modulotone function r | Conference | 2 |
Issue | ISSN | Citations |
1 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshimasa Ishii | 1 | 110 | 17.03 |
| Kazuhisa Makino | 2 | 1088 | 102.74 |