Characterizations and directed path-width of sequence digraphs

DOI10.1007/s00224-022-10104-wzbMath1512.05156arXiv1811.02259OpenAlexW2900280974MaRDI QIDQ6038712

Frank Gurski, Jochen Rethmann, Carolin Rehs

Publication date: 2 May 2023

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

digraphstransitive tournamentsdirected path-widthXP-algorithm

Mathematics Subject Classification ID

Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of the FIFO stack-up problem
• Computing directed pathwidth in \(O(1.89^n)\) time
• Computing the pathwidth of directed graphs with small vertex cover
• A note on exact algorithms for vertex ordering problems on graphs
• Tournament immersion and cutwidth
• Digraph searching, directed vertex separation and directed pathwidth
• Graph minors. I. Excluding a forest
• Min Cut is NP-complete for edge weighted trees
• A partial k-arboretum of graphs with bounded treewidth
• On the pathwidth of chordal graphs
• Directed tree-width
• Directed path-width of sequence digraphs
• Directed path-width and monotonicity in digraph searching
• On the Pathwidth of Almost Semicomplete Digraphs
• Complexity of Finding Embeddings in a k-Tree
• Word-Representable Graphs: a Survey
• Linear Layouts in Submodular Systems
• Digraphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Characterizations and directed path-width of sequence digraphs