Linear-time computation of optimal subgraphs of decomposable graphs
From MaRDI portal
Publication:4728259
DOI10.1016/0196-6774(87)90039-3zbMath0618.68058OpenAlexW2016056456WikidataQ29307016 ScholiaQ29307016MaRDI QIDQ4728259
Alan Wong, Marshall W. Bern, Eugene L. Lawler
Publication date: 1987
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(87)90039-3
combinatorial optimizationmatchingtraveling salesmanweighted graphlinear-time algorithmscomputational graph theoryirredundance number of a tree
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (66)
The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ \(k\)-NLC graphs and polynomial algorithms ⋮ On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Tree-edges deletion problems with bounded diameter obstruction sets ⋮ Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs ⋮ Parametric problems on graphs of bounded tree-width ⋮ Optimal parametric search on graphs of bounded tree-width ⋮ Regular-factors in the complements of partial k-trees ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Minimum-maximal matching in series-parallel graphs ⋮ Nonserial dynamic programming formulations of satisfiability ⋮ Practical algorithms on partial k-trees with an application to domination-like problems ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Unnamed Item ⋮ Generalized coloring for tree-like graphs ⋮ Linear time algorithms for NP-hard problems restricted to partial k- trees ⋮ Using maximality and minimality conditions to construct inequality chains ⋮ Maximal irredundant functions ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ Converting triangulations to quadrangulations ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ A linear algorithm for the pos/neg-weighted 1-median problem on a cactus ⋮ Efficient algorithms for solving systems of linear equations and path problems ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Matchability and \(k\)-maximal matchings ⋮ Tangle bases: Revisited ⋮ The price of anarchy in series-parallel network congestion games ⋮ Improving spanning trees by upgrading nodes ⋮ Branch decomposition heuristics for linear matroids ⋮ On minimum dominating sets with minimum intersection ⋮ Cycle-maximal triangle-free graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Algorithms for recognition of regular properties and decomposition of recursive graph families ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ LP Formulations for Polynomial Optimization Problems ⋮ Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families ⋮ Cross-series-parallel digraphs ⋮ Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Efficient sets in graphs ⋮ Parallel recognition of series-parallel graphs ⋮ Treewidth computations. I: Upper bounds ⋮ Complexity analysis for maximum flow problems with arc reversals ⋮ Complexity of path-forming games ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Efficiently parallelizable problems on a class of decomposable graphs ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ A note on trees, tables, and algorithms ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ A Parametrized Analysis of Algorithms on Hierarchical Graphs ⋮ Gainfree Leontief substitution flow problems ⋮ Irredundance ⋮ Analyse de sensibilité pour les problèmes linéaires en variables 0-1 ⋮ Modifying edges of a network to obtain short subgraphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ Dynamic algorithms for graphs of bounded treewidth ⋮ Bicriteria Network Design Problems ⋮ Tree decompositions and social graphs ⋮ On budget-constrained flow improvement. ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ New limits of treewidth-based tractability in optimization
This page was built for publication: Linear-time computation of optimal subgraphs of decomposable graphs
