Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
From MaRDI portal
Publication:1899445
DOI10.1007/BF01293664zbMath0833.68089OpenAlexW2093476384MaRDI QIDQ1899445
Publication date: 9 October 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01293664
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
