Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
From MaRDI portal
Publication:5042454
DOI10.1007/978-3-030-42071-0_10OpenAlexW3017738900MaRDI QIDQ5042454
Publication date: 19 October 2022
Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.07968
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pattern matching for permutations
- Largest chordal and interval subgraphs faster than \(2^n\)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Excluded permutation matrices and the Stanley-Wilf conjecture
- The complexity of computing the permanent
- Exact exponential algorithms.
- Graph minors. III. Planar tree-width
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- On two techniques of combining branching and treewidth
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Pathwidth of cubic graphs and exact algorithms
- Tree clustering for constraint networks
- S-functions for graphs
- All structured programs have small tree width and good register allocation
- Quickly excluding a planar graph
- Counting \(H-\)colorings of partial \(k-\)trees
- Which problems have strongly exponential complexity?
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Exact algorithms for maximum independent set
- Finding and counting permutations via CSPs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Fast algorithms for max independent set
- The complexity of polynomial-time approximation
- On non-serial dynamic programming
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
- Planar Subgraph Isomorphism Revisited
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- A measure & conquer approach for the analysis of exact algorithms
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
- On Complexity of the Subpattern Problem
- Counting Paths and Packings in Halves
- Planar Capacitated Dominating Set Is W[1-Hard]
- An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
- Algorithms for maximum independent sets
- Finding a Maximum Independent Set
- Color-coding
- Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
- Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
- The Parameterized Complexity of Counting Problems
- LIMITS and Applications of Group Algebras for Parameterized Problems
- Homomorphisms are a good basis for counting small subgraphs
- Coloring Graphs with Constraints on Connectivity
- Surprising Applications of Treewidth Bounds for Planar Graphs
- An Experimental Study of the Treewidth of Real-World Graph Data
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
- Bidimensional Parameters and Local Treewidth
- Counting Matchings of Size k Is $\sharp$ W[1-Hard]
- Finding small patterns in permutations in linear time
- A subexponential parameterized algorithm for Subset TSP on planar graphs
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Operations with structures
- On the complexity of \(k\)-SAT
