Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)

被引：8

作者：

Gurski, Frank ^{[1
]}

Hoffmann, Stefan ^{[1
]}

Komander, Dominique ^{[1
]}

Rehs, Carolin ^{[1
]}

Rethmann, Jochen ^{[2
]}

Wanke, Egon ^{[1
]}

机构：

[1] Heinrich Heine Univ, Inst Comp Sci, D-40225 Dusseldorf, Germany

[2] Niederrhein Univ Appl Sci, Fac Elect Engn & Comp Sci, D-47805 Krefeld, Germany

来源：

SOFSEM 2020: THEORY AND PRACTICE OF COMPUTER SCIENCE | 2020年 / 12011卷

关键词：

Directed co-graphs; Directed Steiner path cover problem; ALGORITHM;

D O I：

10.1007/978-3-030-38919-2_45

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph G = (V (G), E(G)) and a set T subset of V (G) of so-called terminal vertices, the problem is to find a minimum number of directed vertex-disjoint paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute a minimum Steiner path cover for directed cographs in linear time. For T = V (G), the algorithm computes a directed Hamiltonian path if such a path exists.

引用

页码：556 / 565

页数：10

共 12 条

[1] The Euclidean Bottleneck Steiner Path Problem and Other Applications of (α,β)-Pair Decomposition [J].

Abu-Affash, A. Karim ;

Carmi, Paz ;

Katz, Matthew J. ;

Segal, Michael .

DISCRETE & COMPUTATIONAL GEOMETRY, 2014, 51 (01) :1-23

[2] Arc-Disjoint Paths in Decomposable Digraphs [J].

Bang-Jensen, Jorgen ;

Maddaloni, Alessandro .

JOURNAL OF GRAPH THEORY, 2014, 77 (02) :89-110

[3]

Bechet D, 1997, LECT NOTES COMPUT SC, V1232, P230

[4] The Steiner connectivity problem [J].

Borndoerfer, Ralf ;

Karbstein, Marika ;

Pfetsch, Marc E. .

MATHEMATICAL PROGRAMMING, 2013, 142 (1-2) :133-167

[5] COMPLEMENT REDUCIBLE GRAPHS [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174

[6] Fully dynamic recognition algorithm and certificate for directed cographs [J].

Crespelle, C. ;

Paul, C. .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (12) :1722-1741

[7] Computing Digraph Width Measures on Directed Co-graphs (Extended Abstract) [J].

Gurski, Frank ;

Komander, Dominique ;

Rehs, Carolin .

FUNDAMENTALS OF COMPUTATION THEORY, FCT 2019, 2019, 11651 :292-305

[8] Directed Path-Width and Directed Tree-Width of Directed Co-graphs [J].

Gurski, Frank ;

Rehs, Carolin .

COMPUTING AND COMBINATORICS (COCOON 2018), 2018, 10976 :255-267

[9] Directed NLC-width [J].

Gurski, Frank ;

Wanke, Egon ;

Yilmaz, Eda .

THEORETICAL COMPUTER SCIENCE, 2016, 616 :1-17

[10] AN OPTIMAL PATH COVER ALGORITHM FOR COGRAPHS [J].

LIN, R ;

OLARIU, S ;

PRUESSE, G .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1995, 30 (08) :75-83

← 1 2 →