@article{doi:10.1137/S0097539793251219,
    author = {Bodlaender, Hans L.},
    title = {A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth},
    journal = {SIAM Journal on Computing},
    volume = {25},
    number = {6},
    pages = {1305-1317},
    year = {1996},
    doi = {10.1137/S0097539793251219},
    URL = {https://doi.org/10.1137/S0097539793251219},
    eprint = {https://doi.org/10.1137/S0097539793251219},
    abstract = {In this paper, we give for constant k a linear-time algorithm that, given a graph \$G = (V,E)\$, determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant k. },
    date-added = {2023-11-5 23:41:48 +0100}
}

@article{doi:10.1137/S0097539793251219, author = {Bodlaender, Hans L.}, title = {A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth}, journal = {SIAM Journal on Computing}, volume = {25}, number = {6}, pages = {1305-1317}, year = {1996}, doi = {10.1137/S0097539793251219}, URL = {https://doi.org/10.1137/S0097539793251219}, eprint = {https://doi.org/10.1137/S0097539793251219}, abstract = {In this paper, we give for constant k a linear-time algorithm that, given a graph \$G = (V,E)\$, determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant k. }, date-added = {2023-11-5 23:41:48 +0100} }