Non-Preemptive Tree Packing

Stefan Lendl; Gerhard Woeginger; Lasse Wulf

doi:10.1007/s00453-022-01026-7

Non-Preemptive Tree Packing

Stefan Lendl, Gerhard Woeginger, Lasse Wulf^*

^*Korrespondierende/r Autor/-in für diese Arbeit

Institut für Diskrete Mathematik (5050)

Publikation: Beitrag in einer Fachzeitschrift › Artikel › Begutachtung

Abstract

An instance of the non-preemptive tree packing problem consists of an undirected graph G=(V,E) together with a weight w(e) for every edge e∈E. The goal is to activate every edge e for some time interval of length w(e), such that the activated edges keep G 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.

Originalsprache	englisch
Fachzeitschrift	Algorithmica
Frühes Online-Datum	23 Aug. 2022
DOIs	https://doi.org/10.1007/s00453-022-01026-7
Publikationsstatus	Elektronische Veröffentlichung vor Drucklegung. - 23 Aug. 2022

ASJC Scopus subject areas

Angewandte Mathematik
Allgemeine Computerwissenschaft
Angewandte Informatik

Zugriff auf Dokument

10.1007/s00453-022-01026-7Lizenz: CC BY 4.0

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

DK Diskrete Mathematik
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Projekt: Forschungsprojekt

Dieses zitieren

@article{3a3a1d4aeb2f4b8ea206ee8e3d0d174b,

title = "Non-Preemptive Tree Packing",

abstract = "An instance of the non-preemptive tree packing problem consists of an undirected graph G=(V,E) together with a weight w(e) for every edge e∈E. The goal is to activate every edge e for some time interval of length w(e), such that the activated edges keep G 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.",

keywords = "Spanning tree packing, Non-preemptive scheduling, Combinatorial optimization, Timevarying graphs, Keeping a network connected over time",

author = "Stefan Lendl and Gerhard Woeginger and Lasse Wulf",

year = "2022",

month = aug,

day = "23",

doi = "10.1007/s00453-022-01026-7",

language = "English",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

}

TY - JOUR

T1 - Non-Preemptive Tree Packing

AU - Lendl, Stefan

AU - Woeginger, Gerhard

AU - Wulf, Lasse

PY - 2022/8/23

Y1 - 2022/8/23

N2 - An instance of the non-preemptive tree packing problem consists of an undirected graph G=(V,E) together with a weight w(e) for every edge e∈E. The goal is to activate every edge e for some time interval of length w(e), such that the activated edges keep G 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.

AB - An instance of the non-preemptive tree packing problem consists of an undirected graph G=(V,E) together with a weight w(e) for every edge e∈E. The goal is to activate every edge e for some time interval of length w(e), such that the activated edges keep G 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.

KW - Spanning tree packing

KW - Non-preemptive scheduling

KW - Combinatorial optimization

KW - Timevarying graphs

KW - Keeping a network connected over time

UR - http://www.scopus.com/inward/record.url?scp=85136878884&partnerID=8YFLogxK

U2 - 10.1007/s00453-022-01026-7

DO - 10.1007/s00453-022-01026-7

M3 - Article

SN - 0178-4617

JO - Algorithmica

JF - Algorithmica

ER -

Non-Preemptive Tree Packing

Abstract

ASJC Scopus subject areas

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

DK Diskrete Mathematik

Dieses zitieren