Practical algorithms on partial k-trees with an application to domination-like problems
From MaRDI portal
Publication:5060153
DOI10.1007/3-540-57155-8_284zbMath1504.68183OpenAlexW1580414818MaRDI QIDQ5060153
Andrzej Proskurowski, Jan Arne Telle
Publication date: 18 January 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-57155-8_284
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ An asymptotic analysis of labeled and unlabeled \(k\)-trees ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Tree decompositions of graphs: saving memory in dynamic programming ⋮ Restrained and Total Restrained Domination in Graphs ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ Unnamed Item ⋮ Graph limits of random graphs from a subset of connected k‐trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Algorithms finding tree-decompositions of graphs
- Easy problems for tree-decomposable graphs
- Characterization and Recognition of Partial 3-Trees
- Graph minors. II. Algorithmic aspects of tree-width
- Linear-time computability of combinatorial problems on series-parallel graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
This page was built for publication: Practical algorithms on partial k-trees with an application to domination-like problems
