A Note on Directed Treewidth
From MaRDI portal
Publication:6326541
arXiv1910.01826MaRDI QIDQ6326541FDOQ6326541
Authors: Sebastian Wiederrecht 
Publication date: 4 October 2019
Abstract: We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V (D) where every hyperedge corresponds to a directed cycle in D, and the directed treewidth of D. Based on this we show that a digraph has directed treewidth one if and only if its cycle hypergraph is a hypertree.
Directed graphs (digraphs), tournaments (05C20) Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Graph minors (05C83)
This page was built for publication: A Note on Directed Treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326541)
