scientific article; zbMATH DE number 176761

MaRDI QIDQ4036591zbMATH OpenFDO

Authors Jens Lagergren, Stefan Arnborg

Publication date 18 May 1993

zbMATH Keywords

boundlinear time algorithmminimal forbidden minorsfinite congruencegraphs of bounded tree- width

Mathematics Subject Classification ID

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

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

(32)

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

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)