scientific article; zbMATH DE number 475614

zbMath0791.05094MaRDI QIDQ4273870

Michael R. Fellows, Karl A. Abrahamson

Publication date: 28 June 1994

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

bandwidthtreewidthHamiltonian graphscutwidthMyhill-Nerode theoremwell-quasi- order\(t\)-boundaried graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Graph theory (05C99) Eulerian and Hamiltonian graphs (05C45)

Related Items (35)

A Retrospective on (Meta) Kernelization ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ A note on multiflows and treewidth ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ Approximation algorithms for treewidth ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Constructive linear time algorithms for branchwidth ⋮ \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling] ⋮ Sparse obstructions for minor-covering parameters ⋮ Recognizable sets of graphs of bounded tree-width ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Dynamic algorithms for graphs with treewidth 2 ⋮ On reduction algorithms for graphs with small treewidth ⋮ Reduction algorithms for constructing solutions in graphs with small treewidth ⋮ The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs ⋮ Unnamed Item ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Explicit linear kernels for packing problems ⋮ Advice classes of parametrized tractability ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Branch-width, parse trees, and monadic second-order logic for matroids. ⋮ Unnamed Item ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Derivation of algorithms for cutwidth and related graph layout parameters ⋮ Bidimensionality and Kernels ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ On computing graph minor obstruction sets ⋮ The recognizability of sets of graphs is a robust property ⋮ Reduction algorithms for graphs of small treewidth ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ Myhill-Nerode Methods for Hypergraphs

This page was built for publication: