• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms - ESA 2006; Lecture Notes in Computer Science; 4168 >Minimum Transversals in Posi-modular Systems
【24h】

Minimum Transversals in Posi-modular 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 is contained in V of the minimum cardinality such that f(X) ≥ d(X) for all X is contained in 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 posi-modular 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 posi-modular 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），我们认为找到集合R包含在V的V中的问题V_R中包含所有X的f（X）≥d（X）的最小基数，其中该问题可视为源位置问题和（无向）图中的外部网络问题的自然概括。超图。在某些条件下，我们给出（V，f，d）的最小缺陷集的结构表征。我们证明如果f为正模且d为模调（即V的每个非空子集X都有一个元素v∈X使得所有子集d（Y）≥d（X），则所有此类集合都形成树超图。包含v）的X的x的个数，并且相反，任何树超图都可以由正模函数f和模音函数d的最小（V，f，d）不足集表示。通过使用该特征，如果f另外是子模的，并且对于函数p，d由d（X）= max {p（v）∣ v∈X}给出，则我们提出多项式时间算法。 +或d（X）= max {r（v，w）∣ v∈X，w∈V-X}对于函数r：V〜2→R_ +。我们的结果为超图中的源位置问题以及图和超图中的外部网络问题提供了第一个多项式时间算法。我们还表明，即使f为亚模且d≡0，该问题也是棘手的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号