Fixed-Parameter Tractability of Treewidth and Pathwidth (Q2908539)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Fixed-Parameter Tractability of Treewidth and Pathwidth	scientific article

Statements

scholarly article

0 references

Fixed-Parameter Tractability of Treewidth and Pathwidth (English)

0 references

The Multivariate Algorithmic Revolution and Beyond

0 references

publication date

5 September 2012

0 references

Hans L. Bodlaender

0 references

describes a project that uses

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-642-30891-8_12

0 references

Approximation algorithms for treewidth

0 references

An algorithm for the Tutte polynomials of graphs of bounded treewidth

0 references

Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey

0 references

Complexity of Finding Embeddings in a <i>k</i>-Tree

0 references

An algebraic theory of graph reduction

0 references

Easy problems for tree-decomposable graphs

0 references

Characterization and Recognition of Partial 3-Trees

0 references

Linear time algorithms for NP-hard problems restricted to partial k- trees

0 references

Linear-time computation of optimal subgraphs of decomposable graphs

0 references

0 references

Quickly excluding a forest

0 references

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

0 references

Improved self-reduction algorithms for graphs with bounded treewidth

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

On problems without polynomial kernels

0 references

The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs

0 references

Derivation of algorithms for cutwidth and related graph layout parameters

0 references

(Meta) Kernelization

0 references

Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree

0 references

Parallel Algorithms with Optimal Speedup for Bounded Treewidth

0 references

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

0 references

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

0 references

Treewidth computations. I: Upper bounds

0 references

Treewidth computations. II. Lower bounds

0 references

The Pathwidth and Treewidth of Cographs

0 references

Reduction algorithms for graphs of small treewidth

0 references

Faster Algorithms on Branch and Clique Decompositions

0 references

Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs

0 references

Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families

0 references

Treewidth and Minimum Fill-in: Grouping the Minimal Separators

0 references

Listing all potential maximal cliques of a graph

0 references

Polynomial-time self-reducibility: theoretical motivations and practical results<sup>∗</sup>

0 references

On computing graph minor obstruction sets

0 references

Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms

0 references

Shortest paths in digraphs of small treewidth. I: Sequential algorithms

0 references

0 references

The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

0 references

The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Monadic second-order evaluations on tree-decomposable graphs

0 references

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

0 references

On Moderately Exponential Time for SAT

0 references

0 references

Counting \(H-\)colorings of partial \(k-\)trees

0 references

Highly connected sets and the excluded grid theorem

0 references

Dynamic programming and planarity: improved tree-decomposition based algorithms

0 references

Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions

0 references

New Limits to Classical and Quantum Instance Compression

0 references

Safe reduction rules for weighted treewidth

0 references

The vertex separation and search number of a graph

0 references

Improved Approximation Algorithms for Minimum Weight Vertex Separators

0 references

0 references

On the complexity of some colorful problems parameterized by treewidth

0 references

Nonconstructive advances in polynomial-time complexity

0 references

0 references

Nonconstructive tools for proving polynomial-time decidability

0 references

On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design

0 references

On search, decision, and the efficiency of polynomial-time algorithms

0 references

Parametric Problems on Graphs of Bounded Tree-Width

0 references

On two techniques of combining branching and treewidth

0 references

Bidimensionality and Geometric Graphs

0 references

New upper bounds on the decomposability of planar graphs

0 references

0 references

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

0 references

0 references

A comparison of structural CSP decomposition methods

0 references

The complexity of subgraph isomorphism for classes of partial k-trees

0 references

0 references

Dynamic algorithms for graphs of bounded treewidth

0 references

Characterizing multiterminal flow networks and computing flows in networks of small treewidth

0 references

On the complexity of \(k\)-SAT

0 references

A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES

0 references

Recognizability equals definability for partial k-paths

0 references

Definability equals recognizability of partial 3-trees and \(k\)-connected partial \(k\)-trees

0 references

Algorithms for generalized vertex-rankings of partial k-trees

0 references

The vertex separation number of a graph equals its path-width

0 references

Treewidth. Computations and approximations

0 references

Courcelle's theorem -- a game-theoretic approach

0 references

A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms

0 references

Solving partial constraint satisfaction problems with tree decomposition

0 references

Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms

0 references

Efficient Parallel Algorithms for Graphs of Bounded Tree-Width

0 references

0 references

0 references

0 references

Black-white pebbles and graph separation

0 references

A Separator Theorem for Planar Graphs

0 references

Applications of a Planar Separator Theorem

0 references

0 references

Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width

0 references

Resilience of partialk-tree networks with edge and node failures

0 references

Algorithms finding tree-decompositions of graphs

0 references

Channel assignment on graphs of bounded treewidth

0 references

Graph minors. I. Excluding a forest

0 references

Graph minors. III. Planar tree-width

0 references

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Graph minors. V. Excluding a planar graph

0 references

Graph minors. VI. Disjoint paths across a disc

0 references

Graph minors. VII: Disjoint paths on a surface

0 references

Graph minors. IV: Tree-width and well-quasi-ordering

0 references

Graph minors. IX: Disjoint crossed paths

0 references

Graph minors. VIII: A Kuratowski theorem for general surfaces

0 references

Graph minors. X: Obstructions to tree-decomposition

0 references

Graph minors. XXII. Irrelevant vertices in linkage problems

0 references

Graph minors. XI: Circuits on a surface

0 references

Graph minors. XII: Distance on a surface

0 references

Graph minors. XIII: The disjoint paths problem

0 references

Graph minors. XIV: Extending an embedding

0 references

Graph minors. XV: Giant steps

0 references

Graph minors. XVII: Taming a vortex

0 references

Graph minors. XVI: Excluding a non-planar graph

0 references

Graph minors. XVIII: Tree-decompositions and well-quasi-ordering

0 references

Graph minors. XIX: Well-quasi-ordering on a surface.

0 references

Graph minors. XX: Wagner's conjecture

0 references

Graph minors. XXI. graphs with unique linkages

0 references

Graph minors XXIII. Nash-Williams' immersion conjecture

0 references

Quickly excluding a planar graph

0 references

On Linear Recognition of Tree-Width at Most Four

0 references

Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

0 references

Call routing and the ratcatcher

0 references

Algorithms for Vertex Partitioning Problems on Partial k-Trees

0 references

Cutwidth I: A linear time fixed parameter algorithm

0 references

Cutwidth II: Algorithms for partial w-trees of bounded degree

0 references

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

0 references

0 references

0 references

A linear algorithm for finding \([g,f]\)-colorings of partial \(k\)-trees

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-3-642-30891-8_12

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2908539

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2908539&oldid=36806321"