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

DOI10.1007/978-3-030-38919-2_45zbMath1440.68188OpenAlexW2999312995MaRDI QIDQ3297784

Stefan Hoffmann, Jochen Rethmann, Dominique Komander, Frank Gurski, Egon Wanke, Carolin Rehs

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-38919-2_45

zbMATH Keywords

directed co-graphsdirected Steiner path cover problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

The knapsack problem with special neighbor constraints ⋮ Computing directed Steiner path covers ⋮ Acyclic coloring parameterized by directed clique-width ⋮ Solutions for subset sum problems with special digraph constraints ⋮ How to compute digraph width measures on directed co-graphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ On characterizations for subclasses of directed co-graphs ⋮ The Steiner cycle and path cover problem on interval graphs

Cites Work

• Directed NLC-width
• Complement reducible graphs
• Directed path-width and directed tree-width of directed co-graphs
• Partial homology relations -- satisfiability in terms of di-cographs
• An optimal path cover algorithm for cographs
• Computing digraph width measures on directed co-graphs (extended abstract)
• The Steiner connectivity problem
• The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition
• Fully dynamic recognition algorithm and certificate for directed cographs
• Arc-Disjoint Paths in Decomposable Digraphs
• A complete axiomatisation for the inclusion of series-parallel partial orders

This page was built for publication: Computing Directed Steiner Path Covers for Directed Co-graphs (Extended Abstract)