scientific article

Publication date: 1988

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

dynamic programming treewidth polynomial time algorithms tree-decomposition partial k-trees graph decision problems local condition compositions restrictions of NP-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (87)

A new approach on locally checkable problems ⋮ Stochastic Sampling of Structural Contexts Improves the Scalability and Accuracy of RNA 3D Module Identification ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Bounding the search number of graph products ⋮ Algorithms, Complexity, and Hans ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ $k$-NLC graphs and polynomial algorithms ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ Tree-edges deletion problems with bounded diameter obstruction sets ⋮ Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ Parametric problems on graphs of bounded tree-width ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Practical algorithms on partial k-trees with an application to domination-like problems ⋮ The monadic second-order logic of graphs. I: Recognizable sets of finite graphs ⋮ Graphical Models and Message-Passing Algorithms: Some Introductory Lectures ⋮ On the complexity of graph reconstruction ⋮ Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ Rerouting shortest paths in planar graphs ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ Multicuts in planar and bounded-genus graphs with bounded number of terminals ⋮ The $k$-strong induced arboricity of a graph ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ Treewidth and gonality of glued grid graphs ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ Maximum matching in multi-interface networks ⋮ A general framework for enumerating equivalence classes of solutions ⋮ All longest cycles in a 2‐connected partial 3‐tree share a common vertex ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ On the complexity of the regenerator location problem treewidth and other parameters ⋮ On the transversal number of rank $k$ hypergraphs ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Induced subgraphs and tree decompositions. II: Toward walls and their line graphs in graphs of bounded degree ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ On integer linear programs for treewidth based on perfect elimination orderings ⋮ The monadic second-order logic of graphs : Definable sets of finite graphs ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications ⋮ Maximum packing for biconnected outerplanar graphs ⋮ Maximum $k$-splittable $s, t$-flows ⋮ Cycle-maximal triangle-free graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ The Space Complexity of k-Tree Isomorphism ⋮ On permuted super-secondary structures of transmembrane $\beta$-barrel proteins ⋮ LP Formulations for Polynomial Optimization Problems ⋮ Maximum packing for $k$-connected partial $k$-trees in polynomial time ⋮ Decomposing SAT Instances with Pseudo Backbones ⋮ Problems with generalized Steiner problems ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ On the intersection graph of the disks with diameters the sides of a convex $n$-gon ⋮ A linear time algorithm for the $3$-neighbour travelling salesman problem on a Halin graph and extensions ⋮ Tree-width of graphs without a $3\times 3$ grid minor ⋮ Complexity of path-forming games ⋮ Approximation algorithms for maximum two-dimensional pattern matching ⋮ Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Graphs of gonality three ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Two strikes against perfect phylogeny ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Cost Minimisation in Multi-interface Networks ⋮ Optimization and Recognition for K 5-minor Free Graphs in Linear Time ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Walking through waypoints ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Computational aspects of optimal strategic network diffusion ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth Graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Finding Paths in Grids with Forbidden Transitions ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ Faster approximation schemes and parameterized algorithms on (odd-)$H$-minor-free graphs ⋮ Integrating and Sampling Cuts in Bounded Treewidth Graphs ⋮ Dynamic programming for graphs on surfaces ⋮ Bicriteria Network Design Problems ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ No easy puzzles: hardness results for jigsaw puzzles ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Critical elements in combinatorially closed families of graph classes ⋮ A generic convolution algorithm for join operations on tree decompositions ⋮ New limits of treewidth-based tractability in optimization

This page was built for publication: