Directed path-width and directed tree-width of directed co-graphs

DOI10.1007/978-3-319-94776-1_22MaRDI QIDQ1790979zbMATH OpenOpenAlexFDO

Authors Frank Gurski, Carolin Rehs

Publication date 4 October 2018

Full work available at URL https://arxiv.org/abs/1806.04457

zbMATH Keywords

directed path-widthdirected tree-widthdirected co-graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Recommendations

• How to compute digraph width measures on directed co-graphs
• Computing Directed Pathwidth in O(1.89 n ) Time
• Computing directed pathwidth in O(1.89ⁿ) time
• The Pathwidth and Treewidth of Cographs
• The pathwidth and treewidth of cographs

Cited in

(17)

• Efficient computation of the oriented chromatic number of recursively defined digraphs
• The knapsack problem with special neighbor constraints
• Computing directed Steiner path covers
• Directed path-width of sequence digraphs
• Characterizations and directed path-width of sequence digraphs
• Directed path-decompositions
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• Directed one-trees
• On characterizations for subclasses of directed co-graphs
• Forbidden directed minors, directed path-width and directed tree-width of tree-like digraphs
• How to compute digraph width measures on directed co-graphs
• A graph theoretic approach to solve special knapsack problems in polynomial time
• Comparing linear width parameters for directed graphs
• Characterizations for special directed co-graphs
• Solutions for subset sum problems with special digraph constraints
• Oriented coloring on recursively defined digraphs
• Computing directed path-width and directed tree-width of recursively defined digraphs

This page was built for publication: Directed path-width and directed tree-width of directed co-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1790979)