Four Shorts Stories on Surprising Algorithmic Uses of Treewidth (Q5042454)

scientific article; zbMATH DE number 7604209

Language	Label	Description	Also known as
English	Four Shorts Stories on Surprising Algorithmic Uses of Treewidth	scientific article; zbMATH DE number 7604209

Statements

instance of

scholarly article

0 references

title

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth (English)

0 references

author

Dániel Marx

0 references

published in

Treewidth, Kernels, and Algorithms

0 references

publication date

19 October 2022

0 references

full work available at URL

https://arxiv.org/abs/2008.07968

0 references

zbMATH Keywords

treewidth

0 references

parameterized complexity

0 references

fixed-parameter tractability

0 references

bidimensionality

0 references

describes a project that uses

HyperBench

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Coloring Graphs with Constraints on Connectivity

0 references

On Complexity of the Subpattern Problem

0 references

Q4474102

0 references

Color-coding

0 references

Q4252376

0 references

Finding and counting permutations via CSPs

0 references

On non-serial dynamic programming

0 references

Counting Paths and Packings in Halves

0 references

Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time

0 references

Largest chordal and interval subgraphs faster than $2^n$

0 references

Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

0 references

A $c^k n$ 5-Approximation Algorithm for Treewidth

0 references

Planar Capacitated Dominating Set Is W[1]-Hard

0 references

Q3424888

0 references

Pattern matching for permutations

0 references

An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs

0 references

Fast algorithms for max independent set

0 references

The complexity of polynomial-time approximation

0 references

Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems

0 references

Counting Matchings of Size k Is $\sharp$ W[1]-Hard

0 references

Homomorphisms are a good basis for counting small subgraphs

0 references

Improving TSP Tours Using Dynamic Programming over Tree Decompositions.

0 references

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

0 references

Solving the 2-disjoint connected subgraphs problem faster than $2^n$

0 references

Tree clustering for constraint networks

0 references

Bidimensional Parameters and Local Treewidth

0 references

Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs

0 references

Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs

0 references

Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

0 references

Counting $H-$colorings of partial $k-$trees

0 references

Dynamic programming and planarity: improved tree-decomposition based algorithms

0 references

Planar Subgraph Isomorphism Revisited

0 references

Beyond bidimensionality: parameterized subexponential algorithms on directed graphs

0 references

Catalan structures and dynamic programming in $H$-minor-free graphs

0 references

Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions

0 references

The Parameterized Complexity of Counting Problems

0 references

On two techniques of combining branching and treewidth

0 references

A measure & conquer approach for the analysis of exact algorithms

0 references

Pathwidth of cubic graphs and exact algorithms

0 references

Exact exponential algorithms.

0 references

Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms

0 references

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

0 references

Improved bounds on the planar branchwidth with respect to the largest grid minor size

0 references

Finding small patterns in permutations in linear time

0 references

S-functions for graphs

0 references

On the complexity of $k$-SAT

0 references

Which problems have strongly exponential complexity?

0 references

An O(20.304n) Algorithm for Solving Maximum Independent Set Problem

0 references

A subexponential parameterized algorithm for Subset TSP on planar graphs

0 references

A Fine-grained Analysis of a Simple Independent Set Algorithm

0 references

Q5585020

0 references

LIMITS and Applications of Group Algebras for Parameterized Problems

0 references

Q2957518

0 references

Operations with structures

0 references

An Experimental Study of the Treewidth of Real-World Graph Data

0 references

Excluded permutation matrices and the Stanley-Wilf conjecture

0 references

Q4779170

0 references

Surprising Applications of Treewidth Bounds for Planar Graphs

0 references

Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs

0 references

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

0 references

Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3

0 references

Quickly excluding a planar graph

0 references

Graph minors. III. Planar tree-width

0 references

Algorithms for maximum independent sets

0 references

Linear-programming design and analysis of fast algorithms for Max 2-CSP

0 references

Finding a Maximum Independent Set

0 references

All structured programs have small tree width and good register allocation

0 references

The complexity of computing the permanent

0 references

Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs

0 references

Exact algorithms for maximum independent set

0 references

Identifiers

DOI

10.1007/978-3-030-42071-0_10

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5042454