2011 | OriginalPaper | Buchkapitel
A Polynomial Time Algorithm for Bounded Directed Pathwidth
verfasst von : Hisao Tamaki
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
(
m
n
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.