Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs

DOI10.1007/BF01293664zbMath0833.68089OpenAlexW2093476384MaRDI QIDQ1899445

Richard B. Borie

Publication date: 9 October 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01293664

zbMATH Keywords

dynamic programmingpolynomial-time algorithmstree-decomposable graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Fixed-Parameter Tractability of Treewidth and Pathwidth, Complexity of the Packing Coloring Problem for Trees, Paths of bounded length and their cuts: parameterized complexity and algorithms, Practical algorithms for MSO model-checking on tree-decomposable graphs, Complexity of the packing coloring problem for trees, Bounded treewidth as a key to tractability of knowledge representation and reasoning, On minimum cuts and the linear arrangement problem, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, Algorithms for generalized vertex-rankings of partial k-trees, The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

• Hyperedge replacement: grammars and languages
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Minimum-maximal matching in series-parallel graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On minimum dominating sets with minimum intersection
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithms finding tree-decompositions of graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Steiner trees, partial 2–trees, and minimum IFI networks
• Easy problems for tree-decomposable graphs
• Disjoint Paths—A Survey
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• Characterization and Recognition of Partial 3-Trees
• The NP-completeness column: an ongoing guide
• Complexity of Finding Embeddings in a k-Tree
• Graph expressions and graph rewritings
• On multiple steiner subgraph problems
• The Recognition of Series Parallel Digraphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Deterministic Dcomposition of Recursive Graph Classes
• Linear-time computation of optimal subgraphs of decomposable graphs
• 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