Temporal graph classes: A view through temporal separators

被引：35

作者：

Fluschnik, Till ^{[1
]}

Molter, Hendrik ^{[1
]}

Niedermeier, Rolf ^{[1
]}

Renken, Malte ^{[1
]}

Zschoche, Philipp ^{[1
]}

机构：

[1] TU Berlin, Fac 4, Algorithm & Computat Complex, Berlin, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2020年 / 806卷

关键词：

Temporal paths; Temporal restrictions; Unit interval graphs; NP-completeness; Fixed-parameter tractability; Dynamic programming; COMPLEXITY;

D O I：

10.1016/j.tcs.2019.03.031

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We investigate for temporal graphs the computational complexity of separating two distinct vertices s and z by vertex deletion. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding TEMPORAL (s, z)-SEPARATION problem is NP-complete, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph-there we observe polynomial-time solvability in the case of bounded treewidth-as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：197 / 218

页数：22

共 32 条

[1] Temporal Flows in Temporal Networks [J].

Akrida, Eleni C. ;

Czyzowicz, Jurek ;

Gasieniec, Leszek ;

Kuszner, Lukasz ;

Spirakis, Paul G. .

ALGORITHMS AND COMPLEXITY (CIAC 2017), 2017, 10236 :43-54

[2] The Complexity of Optimal Design of Temporally Connected Graphs [J].

Akrida, Eleni C. ;

Gasieniec, Leszek ;

Mertzios, George B. ;

Spirakis, Paul G. .

THEORY OF COMPUTING SYSTEMS, 2017, 61 (03) :907-944

[3]

[Anonymous], 2013, FUNDAMENTALS PARAMET

[4]

[Anonymous], [No title captured]

[5]

[Anonymous], [No title captured]

[6]

[Anonymous], [No title captured]

[7]

[Anonymous], [No title captured]

[8]

Beineke L.W., 1970, J.Comb.Theory, V9, P129

[9] A ckn 5-APPROXIMATION ALGORITHM FOR TREEWIDTH [J].

Bodlaender, Hans L. ;

Drange, Pal Gronas ;

Dregi, Markus S. ;

Fomin, Fedor V. ;

Lokshtanov, Daniel ;

Pilipczuk, Micha L. .

SIAM JOURNAL ON COMPUTING, 2016, 45 (02) :317-378

[10] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

← 1 2 3 4 →