Treewidth computation and extremal combinatorics
DOI10.1007/S00493-012-2536-ZzbMATH Open1289.05447OpenAlexW2115994533WikidataQ60488532 ScholiaQ60488532MaRDI QIDQ2392037FDOQ2392037
Authors: Fedor V. Fomin, Yngve Villanger 
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
Recommendations
treewidthexact algorithmgraph algorithmminimal separatorexponential-time algorithmpotential maximal clique
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Treewidth Computation and Extremal Combinatorics
- A Dynamic Programming Approach to Sequencing Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Exact exponential algorithms.
- A partial k-arboretum of graphs with bounded treewidth
- The Travelling Salesman Problem in Bounded Degree Graphs
- Complexity of Finding Embeddings in a k-Tree
- On Exact Algorithms for Treewidth
- Graph minors. II. Algorithmic aspects of tree-width
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- On the Desirability of Acyclic Database Schemes
- Listing all potential maximal cliques of a graph
- Treewidth and minimum fill-in: Grouping the minimal separators
- Exact Algorithms for Treewidth and Minimum Fill-In
- Listing all Minimal Separators of a Graph
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- On generalized graphs
- The Use of Linear Graphs in Gauss Elimination
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Title not available (Why is that?)
- On the Complexity of Computing Treelength
- Counting clique trees and computing perfect elimination schemes in parallel
- A characterisation of rigid circuit graphs
- Finding a Maximum Independent Set
- Title not available (Why is that?)
- Title not available (Why is that?)
- STACS 2005
- Trimmed Moebius inversion and graphs of bounded degree
- Tree-decompositions with bags of small diameter
- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
- Automata, Languages and Programming
Cited In (25)
- Learning tractable Bayesian networks in the space of elimination orders
- On the number of minimal separators in graphs
- Path Contraction Faster Than 2^n
- A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs
- A blossoming algorithm for tree volumes of composite digraphs
- Counting and Enumeration Problems with Bounded Treewidth
- Positive-instance driven dynamic programming for treewidth
- Path contraction faster than \(2^n\)
- Approximately counting locally-optimal structures
- Treewidth Computation and Extremal Combinatorics
- Largest chordal and interval subgraphs faster than \(2^n\)
- Parameterized complexity of secluded connectivity problems
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Tractability of most probable explanations in multidimensional Bayesian network classifiers
- On the Number of Connected Sets in Bounded Degree Graphs
- Experimental Analysis of Treewidth
- The combinatorics of discrete time-trees: theory and open problems
- Computing tree-depth faster than \(2^n\)
- Deletion to scattered graph classes. I: Case of finite number of graph classes
- Finding connected secluded subgraphs
- Large Induced Subgraphs via Triangulations and CMSO
- A revisit of the scheme for computing treewidth and minimum fill-in
- Approximately Counting Locally-Optimal Structures
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- Positive-instance driven dynamic programming for treewidth
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)
