scientific article; zbMATH DE number 176761

MaRDI QIDQ4036591zbMATH OpenFDO

Authors Jens Lagergren, Stefan Arnborg

Publication date 18 May 1993

zbMATH Keywords

boundfinite congruencegraphs of bounded tree- widthlinear time algorithmminimal forbidden minors

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10)

Recommendations

• scientific article; zbMATH DE number 475617
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• On computing graph minor obstruction sets
• scientific article; zbMATH DE number 4144031
• Graph minors. II. Algorithmic aspects of tree-width

Cited in

(36)

• Derivation of algorithms for cutwidth and related graph layout parameters
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• On computing graph minor obstruction sets
• Algorithms and obstructions for linear-width and related search parameters
• Reduction algorithms for graphs of small treewidth
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Typical sequences revisited -- computing width parameters of graphs
• Fixed-parameter tractability of treewidth and pathwidth
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Approximate tree decompositions of planar graphs in linear time
• Characterizing width two for variants of treewidth
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• scientific article; zbMATH DE number 475617 (Why is no real title available?)
• Constructive linear time algorithms for branchwidth
• Treewidth and pathwidth of permutation graphs
• Finite automata as characterizations of minor closed tree families (extended abstract)
• Parallel algorithms with optimal speedup for bounded treewidth
• scientific article; zbMATH DE number 10087 (Why is no real title available?)
• Minor‐order obstructions for the graphs of vertex cover 6
• Finding branch-decompositions of matroids, hypergraphs, and more
• Finding branch-decompositions of matroids, hypergraphs, and more
• Optimizing tree decompositions in MSO
• Computing Tree Decompositions
• Testing superperfection of k-trees
• Obstructions to within a few vertices or edges of acyclic
• A linear fixed parameter tractable algorithm for connected pathwidth
• Approximate tree decompositions of planar graphs in linear time
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• A lower bound for treewidth and its consequences
• An improved parameterized algorithm for treewidth
• Faster parameterized algorithms for modification problems to minor-closed classes
• Graph parameters, universal obstructions, and WQO
• An overview of universal obstructions for graph parameters
• Approximation algorithms for treewidth

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4036591)