Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Graph Minors and Parameterized Algorithm Design - MaRDI portal

Graph Minors and Parameterized Algorithm Design (Q2908540)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Graph Minors and Parameterized Algorithm Design	scientific article

Statements

scholarly article

0 references

Graph Minors and Parameterized Algorithm Design (English)

0 references

Dimitrios M. Thilikos

0 references

The Multivariate Algorithmic Revolution and Beyond

0 references

publication date

5 September 2012

0 references

zbMATH Keywords

graph minors

0 references

parameterized algorithms

0 references

treewidth

0 references

bidimensionality

0 references

irrelevant vertex technique

0 references

linkages

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_13

0 references

Fast Minor Testing in Planar Graphs

0 references

0 references

Tight Bounds for Linkages in Planar Graphs

0 references

Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs

0 references

Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

0 references

0 references

Approximation algorithms for treewidth

0 references

Easy problems for tree-decomposable graphs

0 references

Tree decompositions of graphs: saving memory in dynamic programming

0 references

On obstructions to small face covers in planar graphs

0 references

Fourier meets M\"{o}bius: fast subset convolution

0 references

(Meta) Kernelization

0 references

0 references

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

0 references

Beyond <i>NP</i>-completeness for problems of bounded width (extended abstract)

0 references

0 references

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

0 references

On the existence of subexponential parameterized algorithms

0 references

On computing graph minor obstruction sets

0 references

The structure of obstructions to treewidth and pathwidth

0 references

0 references

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

0 references

Domination Problems in Nowhere-Dense Classes

0 references

Bidimensional Parameters and Local Treewidth

0 references

Subexponential parameterized algorithms on bounded-genus graphs and <i>H</i> -minor-free graphs

0 references

0 references

Linearity of grid minors in treewidth with applications through bidimensionality

0 references

Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction

0 references

The Bidimensional Theory of Bounded-Genus Graphs

0 references

0 references

Highly connected sets and the excluded grid theorem

0 references

0 references

Dynamic Programming and Fast Matrix Multiplication

0 references

Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus

0 references

0 references

Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions

0 references

The vertex separation and search number of a graph

0 references

Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology

0 references

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

0 references

Contraction obstructions for treewidth

0 references

0 references

0 references

Subexponential algorithms for partial cover problems

0 references

Bidimensionality and Geometric Graphs

0 references

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up

0 references

The complexity of first-order and monadic second-order logic revisited

0 references

0 references

0 references

The intersection graphs of subtrees in trees are exactly the chordal graphs

0 references

On the excluded minors for the matroids of branch-width \(k\)

0 references

Obstructions for Tree-depth

0 references

Induced Packing of Odd Cycles in a Planar Graph

0 references

Finding topological subgraphs is fixed-parameter tractable

0 references

Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size

0 references

Parameterized Complexity of Vertex Deletion into Perfect Graph Classes

0 references

0 references

Ordering by Divisibility in Abstract Algebras

0 references

Parameterizing cut sets in a graph by the number of their components

0 references

The NP-completeness column: An ongoing guide

0 references

0 references

0 references

Planarity Allowing Few Error Vertices in Linear Time

0 references

0 references

An Improved Algorithm for the Half-Disjoint Paths Problem

0 references

The disjoint paths problem in quadratic time

0 references

Linkless and flat embeddings in 3-space and the unknot problem

0 references

0 references

Hadwiger's conjecture is decidable

0 references

Odd cycle packing

0 references

A Practical Approach to Courcelle's Theorem

0 references

Courcelle's theorem -- a game-theoretic approach

0 references

0 references

Directed Nowhere Dense Classes of Graphs

0 references

Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

0 references

Efficient Parallel Algorithms for Graphs of Bounded Tree-Width

0 references

Upper bounds on the size of obstructions and intertwines

0 references

0 references

Graph minor theory

0 references

Chordal deletion is fixed-parameter tractable

0 references

Obtaining a planar graph by vertex deletion

0 references

A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface

0 references

0 references

On Ordered Division Rings

0 references

0 references

The Structure and Number of Obstructions to Treewidth

0 references

Polynomial treewidth forces a large grid-like-minor

0 references

Graph minors. I. Excluding a forest

0 references

Graph minors. III. Planar tree-width

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Graph minors. V. Excluding a planar graph

0 references

Graph minors. X: Obstructions to tree-decomposition

0 references

Graph minors. XXII. Irrelevant vertices in linkage problems

0 references

Graph minors. XIII: The disjoint paths problem

0 references

Graph minors. XVII: Taming a vortex

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

Dynamic Programming for Graphs on Surfaces

0 references

Outerplanar Obstructions for the Feedback Vertex Set

0 references

Minimal acyclic forbidden minors for the family of graphs with bounded path-width

0 references

Algorithms and obstructions for linear-width and related search parameters

0 references

0 references

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

0 references

Girths of bipartite sextet graphs

0 references

Identifiers

zbMATH Open document ID

0 references

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

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2908540

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