Treewidth computation and extremal combinatorics

DOI10.1007/s00493-012-2536-zzbMath1289.05447OpenAlexW2115994533WikidataQ60488532 ScholiaQ60488532MaRDI QIDQ2392037

Yngve Villanger, Fedor V. Fomin

Publication date: 6 August 2013

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-012-2536-z

zbMATH Keywords

graph algorithmtreewidthexact algorithmminimal separatorexponential-time algorithmpotential maximal clique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (21)

Experimental Analysis of Treewidth ⋮ Approximately counting locally-optimal structures ⋮ Approximately Counting Locally-Optimal Structures ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ Parameterized complexity of secluded connectivity problems ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Finding connected secluded subgraphs ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Positive-instance driven dynamic programming for treewidth ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ A revisit of the scheme for computing treewidth and minimum fill-in ⋮ Tractability of most probable explanations in multidimensional Bayesian network classifiers ⋮ Path Contraction Faster than $2^n$ ⋮ Computing tree-depth faster than \(2^n\) ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Path Contraction Faster Than 2^n ⋮ On the Number of Minimal Separators in Graphs ⋮ Learning tractable Bayesian networks in the space of elimination orders ⋮ Positive-Instance Driven Dynamic Programming for Treewidth.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• Counting clique trees and computing perfect elimination schemes in parallel
• A partial k-arboretum of graphs with bounded treewidth
• Listing all potential maximal cliques of a graph
• A characterisation of rigid circuit graphs
• Trimmed Moebius inversion and graphs of bounded degree
• Tree-decompositions with bags of small diameter
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• On the Desirability of Acyclic Database Schemes
• The Use of Linear Graphs in Gauss Elimination
• A Dynamic Programming Approach to Sequencing Problems
• The Travelling Salesman Problem in Bounded Degree Graphs
• Treewidth Computation and Extremal Combinatorics
• On the Complexity of Computing Treelength
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Exact Algorithms for Treewidth and Minimum Fill-In
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Finding a Maximum Independent Set
• Listing all Minimal Separators of a Graph
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• On Exact Algorithms for Treewidth
• Automata, Languages and Programming
• On generalized graphs
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• STACS 2005

This page was built for publication: Treewidth computation and extremal combinatorics