scientific article

zbMATH Open0764.68122MaRDI QIDQ4036591FDOQ4036591

Jens Lagergren, Stefan Arnborg

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

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
• Graph minors. II. Algorithmic aspects of tree-width

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)

Cited In (32)

• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Constructive linear time algorithms for branchwidth
• Parallel algorithms with optimal speedup for bounded treewidth
• \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
• Fixed-Parameter Tractability of Treewidth and Pathwidth
• On computing graph minor obstruction sets
• Approximation algorithms for treewidth
• A lower bound for treewidth and its consequences
• Faster parameterized algorithms for modification problems to minor-closed classes
• Title not available (Why is that?)
• Approximate tree decompositions of planar graphs in linear time
• Computing Tree Decompositions
• Myhill-Nerode Methods for Hypergraphs
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Minor‐order obstructions for the graphs of vertex cover 6
• Title not available (Why is that?)
• Finding branch-decompositions of matroids, hypergraphs, and more
• Algorithms and obstructions for linear-width and related search parameters
• Finding Branch-Decompositions of Matroids, Hypergraphs, and More
• Title not available (Why is that?)
• Characterizing width two for variants of treewidth
• Derivation of algorithms for cutwidth and related graph layout parameters
• Treewidth and pathwidth of permutation graphs
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• 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
• Title not available (Why is that?)
• Typical sequences revisited -- computing width parameters of graphs
• A Linear Fixed Parameter Tractable Algorithm for Connected 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)