Tree decomposition and discrete optimization problems: a survey

DOI10.1007/s10559-007-0080-4zbMath1144.90505OpenAlexW2028280572MaRDI QIDQ2480502

Oleg A. Shcherbina

Publication date: 31 March 2008

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-007-0080-4

zbMATH Keywords

triangulationgraphstree decompositiontreesdiscrete optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Uses Software

• symrcm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm to compute a dominating path in an AT-free graph
• Monadic second-order evaluations on tree-decomposable graphs
• On rigid circuit graphs
• Graph minors. III. Planar tree-width
• A vertex incremental approach for maintaining chordality
• Safe separators for treewidth
• The ellipsoid method and its consequences in combinatorial optimization
• Counting clique trees and computing perfect elimination schemes in parallel
• Chordal embeddings of planar graphs
• On treewidth approximations.
• A practical algorithm for making filled graphs minimal
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• On simple characterizations of k-trees
• A characterisation of rigid circuit graphs
• Maximum cardinality search for computing minimal triangulations of graphs
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Elimination form of the Inverse and its Application to Linear Programming
• Tour Merging via Branch-Decomposition
• On the Desirability of Acyclic Database Schemes
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• The Use of Linear Graphs in Gauss Elimination
• Representation of a finite graph by a set of intervals on the real line
• Steiner trees, partial 2–trees, and minimum IFI networks
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Easy problems for tree-decomposable graphs
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• On the tree representation of chordal graphs
• Representations of chordal graphs as subtrees of a tree
• Power of Natural Semijoins
• Computing the Minimum Fill-In is NP-Complete
• Deterministic Dcomposition of Recursive Graph Classes
• Algorithmic Aspects of Vertex Elimination on Graphs
• A New Lower Bound for Tree-Width Using Maximum Cardinality Search
• Solving partial constraint satisfaction problems with tree decomposition
• Algorithms – ESA 2004
• Automata, Languages and Programming
• Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
• Heuristic and metaheuristic methods for computing graph treewidth
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Experimental and Efficient Algorithms
• SOFSEM 2005: Theory and Practice of Computer Science
• A Characterization of Comparability Graphs and of Interval Graphs
• Principles and Practice of Constraint Programming – CP 2004
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Tree decomposition and discrete optimization problems: a survey