scientific article; zbMATH DE number 4121424
From MaRDI portal
Publication:4734761
zbMath0684.68047MaRDI QIDQ4734761
Publication date: 1988
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Related Items (41)
The longest common subsequence problem for sequences with nested arc annotations. ⋮ Bounded clique cover of some sparse graphs ⋮ PLA folding in special graph classes ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ Approximating the pathwidth of outerplanar graphs ⋮ A note on total and list edge-colouring of graphs of tree-width 3 ⋮ The pathwidth and treewidth of cographs ⋮ Optimal parametric search on graphs of bounded tree-width ⋮ Complexity of metric dimension on planar graphs ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ On Radiocoloring Hierarchically Specified Planar Graphs: $$\mathcal{PSPACE}$$ -completeness and Approximations ⋮ Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ The Firefighter Problem: A Structural Analysis ⋮ Fugitive-search games on graphs and related parameters ⋮ Interdiction problems on planar graphs ⋮ On the treewidth of toroidal grids ⋮ On the linear arboricity of graphs with treewidth at most four ⋮ The multi-stripe travelling salesman problem ⋮ Max NP-completeness made easy ⋮ Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ On minimum dominating sets with minimum intersection ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ On the max min vertex cover problem ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ The firefighter problem: further steps in understanding its complexity ⋮ Disjoint paths in sparse graphs ⋮ Complexity of path-forming games ⋮ An approximation algorithm for the minimum co-path set problem ⋮ Domination in graphs with bounded propagation: Algorithms, formulations and hardness results ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Nonempty intersection of longest paths in series-parallel graphs ⋮ Tree-width, path-width, and cutwidth ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ On some optimization problems on \(k\)-trees and partial \(k\)-trees
This page was built for publication:
