scientific article; zbMATH DE number 795221

MaRDI QIDQ4845370zbMATH OpenFDO

Authors Daniel Bienstock, Michael A. Langston

Publication date 11 September 1995

zbMATH Keywords

branchwidthdisjoint paths problemembeddabilitygraph minorspathwidthsurveytreewidth

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3906520
• Some recent progress and applications in graph minor theory
• Algorithmic Graph Minors and Bidimensionality
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minor theory

Cited in

(23)

• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• The complexity of the vertex-minor problem
• New limits of treewidth-based tractability in optimization
• Improved kernels for tracking paths
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• A basic parameterized complexity primer
• Fixed-parameter tractability of treewidth and pathwidth
• Graph minors and parameterized algorithm design
• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• Kernelization: new upper and lower bound techniques
• Finding disjoint paths with different path-costs: Complexity and algorithms
• LP formulations for polynomial optimization problems
• The Graph Minor Theorem Meets Algebra
• Definability in first order theories of graph orderings
• scientific article; zbMATH DE number 5874803 (Why is no real title available?)
• A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Tangle bases: Revisited
• Graph parameters, universal obstructions, and WQO
• On cut polytopes and graph minors
• Linear-time algorithms for problems on planar graphs with fixed disk dimension

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 Q4845370)