Document Search Results

Cáceres, Manuel; Cairo, Massimo; Mumey, Brendan; Rizzi, Romeo; Tomescu, Alexandru I.

A linear-time parameterized algorithm for computing the width of a DAG. (English) Zbl 07538582

Kowalik, Łukasz (ed.) et al., Graph-theoretic concepts in computer science. 47th international workshop, WG 2021, Warsaw, Poland, June 23–25, 2021. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12911, 257-269 (2021).

MSC: 68R10

Cite Review PDF

Full Text: DOI arXiv

Gurski, Frank; Komander, Dominique; Rehs, Carolin

How to compute digraph width measures on directed co-graphs. (English) Zbl 1497.68378

Theor. Comput. Sci. 855, 161-185 (2021).

MSC: 68R10 05C20 68Q25

Cite Review PDF

Full Text: DOI

Gurski, Frank; Komander, Dominique; Rehs, Carolin

Computing digraph width measures on directed co-graphs (extended abstract). (English) Zbl 1534.68165

Gąsieniec, Leszek Antoni (ed.) et al., Fundamentals of computation theory. 22nd international symposium, FCT 2019, Copenhagen, Denmark, August 12–14, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11651, 292-305 (2019).

MSC: 68R10 05C20 68Q25

Cite Review PDF

Full Text: DOI

Kintali, Shiva

Directed width parameters and circumference of digraphs. (English) Zbl 1357.05052

Theor. Comput. Sci. 659, 83-87 (2017).

MSC: 05C20 05C70

Cite Review PDF

Full Text: DOI arXiv

Amiri, Saeed Akhoondian; Kreutzer, Stephan; Rabinovich, Roman

DAG-width is PSPACE-complete. (English) Zbl 1353.68105

Theor. Comput. Sci. 655, Part A, 78-89 (2016).

MSC: 68Q25 05C70 05C75 05C85 68Q17

Cite Review PDF

Full Text: DOI arXiv

Bang-Jensen, Jørgen; Larsen, Tilde My

DAG-width and circumference of digraphs. (English) Zbl 1339.05156

J. Graph Theory 82, No. 2, 194-206 (2016).

MSC: 05C20 05C12 05C85 68Q17

Cite Review PDF

Full Text: DOI arXiv

Amiri, Saeed Akhoondian; Kaiser, Łukasz; Kreutzer, Stephan; Rabinovich, Roman; Siebertz, Sebastian

Graph searching games and width measures for directed graphs. (English) Zbl 1355.05168

Mayr, Ernst W. (ed.) et al., 32nd international symposium on theoretical aspects of computer science, STACS’15, Garching, Germany, March 4–7, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-78-1). LIPIcs – Leibniz International Proceedings in Informatics 30, 34-47 (2015).

MSC: 05C57 68Q17 91A24 91A43