Combinatorial Optimization on Graphs of Bounded Treewidth

No abstract is available for this paper.

• Publication year

  2008

• Venue

  Computer/law journal

• Publication date

  2008-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1093/COMJNL/BXM037
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions

  2010cited by this paper
• Approximation Algorithms for Treewidth

  2010cited by this paper
• Width Parameters Beyond Tree-width and their Applications

  2008cited by this paper
• The Bidimensionality Theory and Its Algorithmic Applications

  2008influential reference
• Invitation to fixed-parameter algorithms

  2007cited by this paper
• Matroid tree-width

  2006cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In

  2006influential reference
• Branch and Tree Decomposition Techniques for Discrete Optimization

  2005cited by this paper
• Planar Branch Decompositions I: The Ratcatcher

  2005cited by this paper
• Improved Fixed-Parameter Algorithms for Two Feedback Set Problems

  2005cited by this paper
• Improved approximation algorithms for minimum-weight vertex separators

  2005cited by this paper
• Treewidth Lower Bounds with Brambles

  2005cited by this paper
• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions

  2005cited by this paper
• Planar Branch Decompositions II: The Cycle Method

  2005cited by this paper
• New Upper Bound Heuristics for Treewidth

  2005cited by this paper
• Contraction and Treewidth Lower Bounds

  2004cited by this paper
• Parameterized Algorithms for Feedback Vertex Set

  2004cited by this paper
• Graph Minors. XX. Wagner's conjecture

  2004influential reference
• Heuristic and metaheuristic methods for computing graph treewidth

  2004cited by this paper
• Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In

  2004influential reference
• On the Tree Width of Ada Programs

  2004cited by this paper
• A Complete Anytime Algorithm for Treewidth

  2004influential reference
• Finding paths and cycles of superpolylogarithmic length

  2004cited by this paper
• Maximum Cardinality Search for Computing Minimal Triangulations of Graphs

  2004cited by this paper
• Necessary Edges in k-Chordalisations of Graphs

  2003cited by this paper
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search

  2003cited by this paper
• New Lower and Upper Bounds for Graph Treewidth

  2003cited by this paper
• Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs

  2002cited by this paper
• Safe Reduction Rules for Weighted Treewidth

  2002cited by this paper
• Solving partial constraint satisfaction problems with tree decomposition

  2002cited by this paper
• The Treewidth of Java Programs

  2002cited by this paper
• Tree decompositions with small cost

  2002influential reference
• Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two1

  2001cited by this paper
• Efficient Approximation for Triangulation of Minimum Treewidth

  2001influential reference
• Exact Algorithms for NP-Hard Problems: A Survey

  2001cited by this paper
• Treewidth: Computational Experiments

  2001influential reference
• On treewidth approximations

  2001cited by this paper
• Memory Requirements for Table Computations in Partial \sl k -Tree Algorithms

  2000cited by this paper
• Frequency assignment : models and algorithms

  1999influential reference
• Memory Requirements for Table Computations in Partial k-tree Algorithms

  1998cited by this paper
• All Structured Programs have Small Tree-Width and Good Register Allocation

  1998cited by this paper
• Hypertree decompositions and tractable queries

  1998cited by this paper
• Parameterized Complexity

  1998cited by this paper
• Treewidth for Graphs with Small Chordality

  1997cited by this paper
• Structured Programs have Small Tree-Width and Good Register Allocation (Extended Abstract)

  1997cited by this paper
• Algorithms for Vertex Partitioning Problems on Partial k-Trees

  1997cited by this paper
• Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms

  1997cited by this paper
• A Practical Algorithm for Finding Optimal Triangulations

  1997cited by this paper
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width

  1996cited by this paper
• Graph Minors: XV. Giant Steps

  1996cited by this paper
• Treewidth

  1994cited by this paper
• Call routing and the ratcatcher

  1994influential reference
• Treewidth: Computations and Approximations

  1994cited by this paper
• On Linear Time Minor Tests with Depth-First Search

  1993cited by this paper
• On Reduction Algorithms for Graphs with Small Treewidth

  1993cited by this paper
• Graph Searching and a Min-Max Theorem for Tree-Width

  1993influential reference
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993cited by this paper
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families

  1992cited by this paper
• Optimal decomposition of probabilistic networks by simulated annealing

  1992cited by this paper
• Finding approximate separators and computing tree width quickly

  1992cited by this paper
• Graph minors. X. Obstructions to tree-decomposition

  1991influential reference
• Monadic Second-Order Evaluations on Tree-Decomposable Graphs

  1991cited by this paper
• Easy Problems for Tree-Decomposable Graphs

  1991influential reference
• The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

  1990cited by this paper
• The Pathwidth and Treewidth of Cographs

  1990cited by this paper
• The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs

  1990cited by this paper
• An algebraic theory of graph reduction

  1990cited by this paper
• Local computations with probabilities on graphical structures and their application to expert systems

  1990cited by this paper
• Tree Clustering for Constraint Networks

  1989cited by this paper
• Linear time algorithms for NP-hard problems restricted to partial k-trees

  1989cited by this paper
• On search decision and the efficiency of polynomial-time algorithms

  1989cited by this paper
• Linear-Time Computation of Optimal Subgraphs of Decomposable Graphs

  1987influential reference
• Complexity of finding embeddings in a k -tree

  1987cited by this paper
• Graph Minors. II. Algorithmic Aspects of Tree-Width

  1986cited by this paper
• Algorithmic graph theory and perfect graphs

  1986cited by this paper
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey

  1985influential reference
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

  1984cited by this paper
• A linear algorithm for the domination number of a series-parallel graph

  1983cited by this paper
• Graph minors. I. Excluding a forest

  1983influential reference
• Approximation algorithms for NP-complete problems on planar graphs

  1983cited by this paper
• Linear-time computability of combinatorial problems on series-parallel graphs

  1982cited by this paper
• Computing the Minimum Fill-in is NP^Complete

  1981cited by this paper
• Linear Algorithms for Edge-Coloring Trees and Unicyclic Graphs

  1979cited by this paper
• A Minimum Linear Arrangement Algorithm for Undirected Trees

  1979cited by this paper
• A Separator Theorem for Planar Graphs

  1977cited by this paper
• Applications of a planar separator theorem

  1977cited by this paper
• Algorithmic Aspects of Vertex Elimination on Graphs

  1976cited by this paper
• The intersection graphs of subtrees in tree are exactly the chordal graphs

  1974cited by this paper
• A GRAPH-THEORETIC STUDY OF THE NUMERICAL SOLUTION OF SPARSE POSITIVE DEFINITE SYSTEMS OF LINEAR EQUATIONS

  1972cited by this paper
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

  1972cited by this paper
• Triangulated graphs and the elimination process

  1970cited by this paper
• Graph theory

  1969cited by this paper
• Konrad-zuse-zentrum F ¨ Ur Informationstechnik Berlin on the Maximum Cardinality Search Lower Bound for Treewidth on the Maximum Cardinality Search Lower Bound for Treewidth *

  year unknowninfluential reference

• Tractable but Hard to Approximate: The Bi‐Objective Minimum s$$ s $$ ‐ t$$ t $$ ‐Cut Problem With Binary Capacities

  2026cites this paper
• Perfect Matching Under Precedence Constraints

  2025cites this paper
• Graph Homomorphism Distortion: A Metric to Distinguish Them All and in the Latent Space Bind Them

  2025cites this paper
• Dynamic Programming Algorithms for Probabilistic Bipolar Argumentation Frameworks

  2025cites this paper
• Treewidth Parameterized by Feedback Vertex Number

  2025cites this paper
• Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing

  2025cites this paper
• SSS Algorithms for Max-Cut

  2025cites this paper
• Bridging Treewidth and Clique-Width via Cograph-Modular-Treewidth

  2025cites this paper
• On integer linear programs for treewidth based on perfect elimination orderings (extended version)

  2025cites this paper
• A Courcelle-Type Metatheorem for Rank-Bounded Unconstrained Binary Optimization

  2025cites this paper
• Computation of Graph Polynomials via Tree Decomposition: Theory, Algorithms, and Python Implementation

  2025cites this paper
• Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach

  2024cites this paper
• Quantitative Claim-Centric Reasoning in Logic-Based Argumentation

  2024cites this paper
• Rejection in Abstract Argumentation: Harder Than Acceptance?

  2024cites this paper
• Infrared: a declarative tree decomposition-powered framework for bioinformatics

  2024cites this paper
• Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization

  2024cites this paper
• Space efficient algorithm for solving reachability using tree decomposition and separators

  2023cites this paper
• Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation

  2023cites this paper
• Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs

  2023cites this paper
• Listing Small Minimal $s,t$-separators in FPT-Delay

  2023cites this paper
• Automatic Exploration of the Natural Variability of RNA Non-Canonical Geometric Patterns with a Parameterized Sampling Technique

  2023cites this paper
• Ranked Enumeration of Minimal Separators

  2023cites this paper
• Automated design of dynamic programming schemes for RNA folding with pseudoknots

  2023cites this paper
• Properties of uniformly 3-connected graphs

  2022cites this paper
• Structure Meets Power Workshop

  2022cites this paper
• From Width-Based Model Checking to Width-Based Automated Theorem Proving

  2022cites this paper
• Solving Projected Model Counting by Utilizing Treewidth and its Limits

  2022cites this paper
• Monoidal Width

  2022cites this paper
• Monoidal Width: Capturing Rank Width

  2022cites this paper
• Monoidal Width

  2022cites this paper
• On computing vertex connectivity of 1-planar graphs

  2022cites this paper
• Density Personalized Group Query

  2022cites this paper
• Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth

  2021cites this paper
• A Generic Convolution Algorithm for Join Operations on Tree Decompositions

  2021cites this paper
• Exploiting Variable Sparsity in Computing Equilibria of Biological Dynamical Systems by Triangular Decomposition

  2021cites this paper
• Anti-factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)

  2021cites this paper
• Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth

  2021cites this paper
• Public Goods Games in Directed Networks

  2021cites this paper
• Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics

  2021cites this paper
• FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More

  2021cites this paper
• Classical Simulation of Boson Sampling Based on Graph Structure.

  2021cites this paper
• Vertex deletion parameterized by elimination distance and even less

  2021cites this paper
• An efficient parameterized approximation scheme for the Star k-Hub Center

  2021cites this paper
• Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs

  2021cites this paper
• Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard

  2020cites this paper
• Minimum color‐degree perfect b‐matchings

  2020cites this paper
• A polynomial time algorithm to compute the connected tree-width of a series-parallel graph

  2020cites this paper
• Fast Algorithms for Join Operations on Tree Decompositions

  2020cites this paper
• Full complexity classification of the list homomorphism problem for bounded-treewidth graphs

  2020cites this paper
• Combinatorial width parameters for 3-dimensional manifolds

  2020cites this paper
• Exploiting Database Management Systems and Treewidth for Counting

  2020cites this paper
• Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth

  2020cites this paper
• Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology

  2020cites this paper
• Beating the Worst-Case: Analysis of a Practical Algorithm for Treewidth

  2020cites this paper
• Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs

  2020cites this paper
• Tree Decomposition-based Approach for Compiling Independent Sets

  2020cites this paper
• Parameterized analysis of complexity

  2020cites this paper
• Algebras for Tree Decomposable Graphs

  2020cites this paper
• Lower Bounds for QBFs of Bounded Treewidth

  2019cites this paper
• Graph fragmentation problem: analysis and synthesis

  2019cites this paper
• Beating Treewidth for Average-Case Subgraph Isomorphism

  2019cites this paper
• Monitoring the Internet of Things (IoT) Networks

  2019influential citation
• Computing Treewidth via Exact and Heuristic Lists of Minimal Separators

  2019cites this paper
• Reachability in High Treewidth Graphs

  2019cites this paper
• Enumerating Potential Maximal Cliques via SAT and ASP

  2019cites this paper
• On the Complexity of Toric Ideals

  2019cites this paper
• 44 : 3 2 Preliminaries 2 . 1 Graphs

  2019cites this paper
• Answer Set Solving exploiting Treewidth and its Limits

  2019cites this paper
• A heuristic use of dynamic programming to upperbound treewidth

  2019cites this paper
• Efficient parallel algorithms for parameterized problems

  2019cites this paper
• Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth Bas

  2019cites this paper
• A Machine Learning Approach to Algorithm Selection for Exact Computation of Treewidth

  2019cites this paper
• On the Rectangular Knapsack Problem - Approximation of a Specific Quadratic Knapsack Problem

  2019cites this paper
• The Convergence of Iterative Delegations in Liquid Democracy

  2018cites this paper
• Solving Treewidth in graphs using MaxSAT

  2018cites this paper
• Parameterized Orientable Deletion

  2018cites this paper
• Multi‐budgeted matching problems

  2018cites this paper
• Committee Selection with Intraclass and Interclass Synergies

  2018cites this paper
• Kernelization of Cycle Packing with Relaxed Disjointness Constraints

  2018cites this paper
• Fast Dynamic Programming on Graph Decompositions

  2018cites this paper
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank

  2018cites this paper
• Finer Tight Bounds for Coloring on Clique-Width

  2018cites this paper
• Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

  2018cites this paper
• Parameterized Orientable Deletion ∗

  2018cites this paper
• Parameterized Algorithms for the Matrix Completion Problem

  2018cites this paper
• Décomposition de graphes en plus courts chemins et en cycles de faible excentricité. (Decomposing a graph with shortest paths of bounded eccentricity)

  2018cites this paper
• Exploiting Treewidth for Projected Model Counting and its Limits

  2018cites this paper
• J un 2 01 8 Fast Dynamic Programming on Graph Decompositions ∗

  2018cites this paper
• Language and Automata Theory and Applications

  2018influential citation
• Parameterized (Approximate) Defective Coloring

  2018cites this paper
• New Perspectives on Multi-Objective Knapsack Problems

  2018cites this paper
• Polynomial systems: graphical structure, geometry, and applications

  2018cites this paper
• Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization

  2018cites this paper
• AC-TR-17-015 December 2017 SAT-Based Local Improvement for Finding Tree Decompositions of SmallWidth

  2018cites this paper
• D S ] 1 0 A pr 2 01 8 Parameterized Algorithms for the Matrix Completion Problem

  2018cites this paper
• Decomposition Structures for Soft Constraint Evaluation Problems: An Algebraic Approach

  2018cites this paper
• Proposal : E � ciently Enumerating Tree Decompositions

  2018cites this paper
• Chordal Graphs in Triangular Decomposition in Top-Down Style

  2018cites this paper
• Can We Create Large k-Cores by Adding Few Edges?

  2018cites this paper
• 3-Manifold triangulations with small treewidth

  2018cites this paper