Treewidth computation and extremal combinatorics
Let \(G=(V,E)\) be a graph. For every \(v \in V\) and all integers \(b,f \geq 0\), the number of connected subsets \(B \subseteq V\) such that \(v \in B\), \(| B| =b+1\) and \(| N(B)| =f\) is at most \(b+f \choose b\). The authors prove this combinatorial lemma and, based on it, develop algorithms that, for a given graph on \(n\) vertices, (1) compute the treewidth in time \(O(1.7549^n)\) using exponential space; (2) compute the treewidth in time \(O(2.6151^n)\) using polynomial space; (3) decide in time \(O(n^5\cdot{\lceil 2n+k+8)/3\rceil \choose k+2})\) whether the treewidth is at most \(k\); (4) list all minimal separators in time \(O(1.6181^n)\); (5) list all potential maximal cliques in time \(O(1.7549^n)\); which improve previously known algorithms for these problems.
- A characterisation of rigid circuit graphs
- A Computing Procedure for Quantification Theory
- A Dynamic Programming Approach to Sequencing Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A machine program for theorem-proving
- A partial k-arboretum of graphs with bounded treewidth
- Automata, Languages and Programming
- Complexity of Finding Embeddings in a k-Tree
- Counting clique trees and computing perfect elimination schemes in parallel
- Exact Algorithms for Treewidth and Minimum Fill-In
- Exact exponential algorithms.
- Finding a Maximum Independent Set
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Graph minors. II. Algorithmic aspects of tree-width
- scientific article; zbMATH DE number 5604103 (Why is no real title available?)
- scientific article; zbMATH DE number 5605070 (Why is no real title available?)
- scientific article; zbMATH DE number 1324671 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 1953201 (Why is no real title available?)
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- Listing all Minimal Separators of a Graph
- Listing all potential maximal cliques of a graph
- On Exact Algorithms for Treewidth
- On generalized graphs
- On the Complexity of Computing Treelength
- On the Desirability of Acyclic Database Schemes
- STACS 2005
- The Travelling Salesman Problem in Bounded Degree Graphs
- The Use of Linear Graphs in Gauss Elimination
- Tree-decompositions with bags of small diameter
- Treewidth and minimum fill-in: Grouping the minimal separators
- Treewidth Computation and Extremal Combinatorics
- Trimmed Moebius inversion and graphs of bounded degree
- A blossoming algorithm for tree volumes of composite digraphs
- Tractability of most probable explanations in multidimensional Bayesian network classifiers
- Finding connected secluded subgraphs
- Learning tractable Bayesian networks in the space of elimination orders
- Parameterized complexity of secluded connectivity problems
- Positive-instance driven dynamic programming for treewidth
- A revisit of the scheme for computing treewidth and minimum fill-in
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- On the number of minimal separators in graphs
- On the Number of Connected Sets in Bounded Degree Graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Approximately counting locally-optimal structures
- Counting and Enumeration Problems with Bounded Treewidth
- Largest chordal and interval subgraphs faster than \(2^n\)
- Path contraction faster than 2ⁿ
- Approximately Counting Locally-Optimal Structures
- Treewidth Computation and Extremal Combinatorics
- Computing tree-depth faster than \(2^n\)
- Experimental Analysis of Treewidth
- A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
- Path Contraction Faster Than 2^n
- Positive-instance driven dynamic programming for treewidth
- Deletion to scattered graph classes. I: Case of finite number of graph classes
- Revisiting path contraction and cycle contraction
- A contraction-recursive algorithm for treewidth
- Revisiting path contraction and cycle contraction
- An FPT algorithm for elimination distance to bounded degree graphs
- A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
- Sauer-Shelah Lemma
- Exploring the closure operator for minimal a, b-separators: insights from Galois connections
- The combinatorics of discrete time-trees: theory and open problems
This page was built for publication: Treewidth computation and extremal combinatorics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392037)
