• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

非抢占式树打包

Non-Preemptive Tree Packing.

作者信息

Lendl Stefan, Woeginger Gerhard, Wulf Lasse

机构信息

Department of Operations and Information Systems, University of Graz, Graz, Styria Austria.

Department of Computer Science, RWTH Aachen, Aachen, North Rhine-Westphalia Germany.

出版信息

Algorithmica. 2023;85(3):783-804. doi: 10.1007/s00453-022-01026-7. Epub 2022 Aug 23.

DOI:10.1007/s00453-022-01026-7
PMID:36883187
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC9984357/
Abstract

An instance of the non-preemptive tree packing problem consists of an undirected graph together with a weight () for every edge . The goal is to activate every edge for some time interval of length (), such that the activated edges keep connected for the longest possible overall time. We derive a variety of results on this problem. The problem is strongly NP-hard even on graphs of treewidth 2, and it does not allow a polynomial time approximation scheme (unless P=NP). Furthermore, we discuss the performance of a simple greedy algorithm, and we construct and analyze a number of parameterized and exact algorithms.

摘要

非抢占式树打包问题的一个实例由一个无向图以及每条边(e)的权重(w(e))组成。目标是在长度为(w(e))的某个时间间隔内激活每条边(e)，使得激活的边在尽可能长的总时间内保持图连通。我们得出了关于这个问题的各种结果。即使在树宽为(2)的图上，该问题也是强NP难的，并且它不允许多项式时间近似方案（除非(P = NP)）。此外，我们讨论了一种简单贪心算法的性能，并构造和分析了一些参数化算法和精确算法。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/46184e54fd36/453_2022_1026_Fig8_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/864408468d29/453_2022_1026_Fig1_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/50014b9cb98d/453_2022_1026_Fig2_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/c0370c89406c/453_2022_1026_Fig3_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/b437298aef96/453_2022_1026_Fig4_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/ff402af4b08b/453_2022_1026_Fig5_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/907897f335c9/453_2022_1026_Fig6_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/0360f8ad6ced/453_2022_1026_Fig7_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/46184e54fd36/453_2022_1026_Fig8_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/864408468d29/453_2022_1026_Fig1_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/50014b9cb98d/453_2022_1026_Fig2_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/c0370c89406c/453_2022_1026_Fig3_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/b437298aef96/453_2022_1026_Fig4_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/ff402af4b08b/453_2022_1026_Fig5_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/907897f335c9/453_2022_1026_Fig6_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/0360f8ad6ced/453_2022_1026_Fig7_HTML.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/a339/9984357/46184e54fd36/453_2022_1026_Fig8_HTML.jpg

相似文献

1
Non-Preemptive Tree Packing.非抢占式树打包
Algorithmica. 2023;85(3):783-804. doi: 10.1007/s00453-022-01026-7. Epub 2022 Aug 23.
2
Treewidth-based algorithms for the small parsimony problem on networks.基于树宽的网络上小简约问题的算法
Algorithms Mol Biol. 2022 Aug 20;17(1):15. doi: 10.1186/s13015-022-00216-w.
3
Parameterized Complexity of Eulerian Deletion Problems.欧拉删除问题的参数复杂性
Algorithmica. 2014;68(1):41-61. doi: 10.1007/s00453-012-9667-x. Epub 2012 Jun 22.
4
The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths.用于计算边不相交路径的基于割的参数的力量。
Algorithmica. 2021;83(2):726-752. doi: 10.1007/s00453-020-00772-w. Epub 2020 Oct 21.
5
The Complexity of Optimal Design of Temporally Connected Graphs.
Theory Comput Syst. 2017;61(3):907-944. doi: 10.1007/s00224-017-9757-x. Epub 2017 Apr 3.
6
Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics.树形分解：降低树宽以解锁RNA生物信息学中的固定参数可解算法
Algorithms Mol Biol. 2022 Apr 2;17(1):8. doi: 10.1186/s13015-022-00213-z.
7
An efficient 3-approximation algorithm for the Steiner tree problem with the minimum number of Steiner points and bounded edge length.带最小 Steiner 点数和有界边长度的 Steiner 树问题的有效 3-近似算法。
PLoS One. 2023 Nov 21;18(11):e0294353. doi: 10.1371/journal.pone.0294353. eCollection 2023.
8
A heuristic method for solving the Steiner tree problem in graphs using network centralities.一种基于网络中心性求解图中斯坦纳树问题的启发式方法。
PLoS One. 2024 Jun 6;19(6):e0303764. doi: 10.1371/journal.pone.0303764. eCollection 2024.
9
A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation.一种基于DNA分子计算的求解最小生成树问题的新型快速算法。
Biosystems. 2013 Oct;114(1):1-7. doi: 10.1016/j.biosystems.2013.07.007. Epub 2013 Jul 16.
10
Parameterized Complexity and Inapproximability of Dominating Set Problem in Chordal and Near Chordal Graphs.弦图和近弦图中支配集问题的参数化复杂性与不可近似性
J Comb Optim. 2010 Apr 15;20(2):1-15. doi: 10.1007/s10878-010-9317-7.