A polynomial time algorithm for bounded directed pathwidth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)

Abstract

We give a polynomial time algorithm for bounded directed pathwidth. Given a positive integer k and a digraph G with n vertices and m edges, it runs in O(mn k + 1) time and constructs a directed path-decomposition of G of width at most k if one exists and otherwise reports the non-existence.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers
Pages331-342
Number of pages12
DOIs
Publication statusPublished - 1 Dec 2011
Event37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 - Tepla Monastery, Czech Republic
Duration: 21 Jun 201124 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6986 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011
CountryCzech Republic
CityTepla Monastery
Period21/06/1124/06/11

Fingerprint Dive into the research topics of 'A polynomial time algorithm for bounded directed pathwidth'. Together they form a unique fingerprint.

  • Cite this

    Tamaki, H. (2011). A polynomial time algorithm for bounded directed pathwidth. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers (pp. 331-342). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6986 LNCS). https://doi.org/10.1007/978-3-642-25870-1_30