...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure
【24h】

On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure

机译：关于最大彩色树状图问题和颜色层次图结构

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let G=(V,A) be a vertex-colored arc-weighted directed acyclic graph (DAG) rooted in some vertex r. The color hierarchy graph H(G) of G is defined as follows: the vertex set of H(G) is the color set C of G, and H(G) has an arc from c to c' if G has an arc from a vertex of color c to a vertex of color c'. We study the Maximum Colorful Arborescence (MCA) problem, which takes as input a DAG G such that H(G) is also a DAG, and aims at finding in G a maximum-weight arborescence rooted in r in which no color appears more than once. The MCA problem models the de novo inference of unknown metabolites by mass spectrometry experiments. Although the problem has been introduced ten years ago (under a different name), it was only recently pointed out that a crucial additional property in the problem definition was missing: by essence, H(G) must be a DAG. In this paper, we further investigate MCA under this new light and provide new algorithmic results for this problem, with a focus on fixed-parameter tractability (FPT) issues for different structural parameters of H(G). In particular, we develop an O^*(3^{{x_H}})-time algorithm for solving MCA, where {x_{H}} is the number of vertices of indegree at least two in H(G), thereby improving the O^*(3^{|C|})-time algorithm of B?cker et al. [Proc. ECCB '08]. We also prove that MCA is W[2]-hard with respect to the treewidth t_H of the underlying undirected graph of H(G), and further show that it is FPT with respect to t_H + l_{C}, where l_{C} := |V| - |C|.
机译：令G =（V，A）是植根于某个顶点r的顶点彩色弧加权有向无环图（DAG）。 G的颜色层次图H（G）定义如下：H（G）的顶点集是G的颜色集C，如果G具有从c到c'的弧，则H（G）从c到c'的弧。颜色c的顶点到颜色c'的顶点。我们研究了最大彩色树状结构（MCA）问题，该问题采用DAG G作为输入，使得H（G）也是DAG，目的是在G中找到根于r的最大权重树状结构，其中不出现颜色大于一旦。 MCA问题通过质谱实验模拟了未知代谢物的从头推断。尽管该问题是十年前（用另一个名称）提出的，但直到最近才指出，该问题定义中缺少一个关键的附加属性：本质上，H（G）必须是DAG。在本文中，我们将在此新情况下进一步研究MCA，并针对此问题提供新的算法结果，重点是针对H（G）不同结构参数的固定参数可延展性（FPT）问题。特别是，我们开发了一种O ^ *（3 ^ {{x_H}}）时间算法来求解MCA，其中{x_ {H}}是H（G）中至少2个度数的顶点的数目，从而提高了B？cker等人的O ^ *（3 ^ {| C |}）时间算法。 [过程ECCB '08]。我们还证明MCA相对于H（G）的基础无向图的树宽t_H是W [2]-硬的，并且进一步证明它相对于t_H + l_ {C}是FPT，其中l_ {C }：= | V | -| C |。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号