...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >MINIMUM TRANSVERSALS IN POSIMODULAR SYSTEMS
【24h】

MINIMUM TRANSVERSALS IN POSIMODULAR SYSTEMS

机译：准系统中的最小横向

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Given a system (V, f, d) on a finite set V consisting of two set functions f : 2~V → R and d : 2~V → R, we consider the problem of finding a set R C V of minimum cardinality such that f(X) ≥ d(X) for all X ? V - R, where the problem can be regarded as a natural generalization of the source location problems and the external network problems in (undirected) graphs and hypergraphs. We give a structural characterization of minimal deficient sets of (V,f,d) under certain conditions. We show that all such sets form a tree hypergraph if f is posimodular and d is modulotone (I.e., each nonempty subset X of V has an element v ∈ X such that d(Y) ≥ d(X) for all subsets Y of X that contain v) and that, conversely, any tree hypergraph can be represented by minimal deficient sets of (V, f, d) for a posimodular function f and a modulotone function d. By using this characterization, we present a polynomial-time algorithm if, in addition, f is submodular and d is given by either d(X) = max{p(v) | v ∈ X} for a function p : V → R_+ or d(X) = max{r(v, w) | v ∈X, w ∈ V - X} for a function r : V~2 → R_+. Our result provides first polynomial-time algorithms for the source location problem in hypergraphs and the external network problems in graphs and hypergraphs. We also show that the problem is intractable, even if f is submodular and d ≡ 0.
机译：给定一个由两个集合函数f：2〜V→R和d：2〜V→R组成的有限集合V上的系统（V，f，d），我们考虑找到最小基数的集合RCV的问题对于所有X？f（X）≥d（X） V-R，其中的问题可以看作是（无向）图和超图中源位置问题和外部网络问题的自然概括。在某些条件下，我们给出（V，f，d）的最小缺陷集的结构表征。我们证明，如果f为正模且d为模调（即，V的每个非空子集X都有一个元素v∈X，则对于X的所有子集d（Y）≥d（X），所有此类集合均形成树超图。包含v），并且反之，对于正模函数f和模调函数d，任何树超图都可以由（V，f，d）的最小亏集表示。通过使用这种表征，如果f另外是子模的，并且d由d（X）= max {p（v）| ||给出，则我们提出了多项式时间算法。函数p的v∈X}：V→R_ +或d（X）= max {r（v，w）|对于函数r：V〜2→R_ +。v∈X，w∈V-X}。我们的结果为超图中的源位置问题以及图和超图中的外部网络问题提供了第一个多项式时间算法。我们还表明，即使f为亚模且d≡0，该问题也是棘手的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号