Linear-time computation of optimal subgraphs of decomposable graphs
From MaRDI portal
DOI10.1016/0196-6774(87)90039-3zbMATH Open0618.68058OpenAlexW2016056456WikidataQ29307016 ScholiaQ29307016MaRDI QIDQ4728259FDOQ4728259
Authors: Alan Wong, M. 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
Recommendations
combinatorial optimizationmatchingweighted graphlinear-time algorithmstraveling salesmancomputational 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)
Cited In (73)
- A note on trees, tables, and algorithms
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Branch decomposition heuristics for linear matroids
- Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks
- Tangle bases: Revisited
- Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs
- Regular-factors in the complements of partial k-trees
- Optimal parametric search on graphs of bounded tree-width
- Irredundance
- The price of anarchy in series-parallel network congestion games
- Definability equals recognizability of partial 3-trees
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Title not available (Why is that?)
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- Minimum-maximal matching in series-parallel graphs
- Nonserial dynamic programming formulations of satisfiability
- Matchability and \(k\)-maximal matchings
- \(k\)-NLC graphs and polynomial algorithms
- Complexity of path-forming games
- Title not available (Why is that?)
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
- Algorithm to find a maximum 2-packing set in a cactus
- Cross-series-parallel digraphs
- Algorithms for recognition of regular properties and decomposition of recursive graph families
- A partial k-arboretum of graphs with bounded treewidth
- A branch-and-price-and-cut method for computing an optimal bramble
- Complexity analysis for maximum flow problems with arc reversals
- Modifying edges of a network to obtain short subgraphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Practical algorithms on partial k-trees with an application to domination-like problems
- Parallel recognition of series-parallel graphs
- Analyse de sensibilité pour les problèmes linéaires en variables 0-1
- Efficiently parallelizable problems on a class of decomposable graphs
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Improving spanning trees by upgrading nodes
- A Parametrized Analysis of Algorithms on Hierarchical Graphs
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- Sublinear randomized algorithms for skeleton decompositions
- Treewidth computations. I: Upper bounds
- Converting triangulations to quadrangulations
- Efficient sets in graphs
- Maximal irredundant functions
- Cycle-maximal triangle-free graphs
- Monadic second-order evaluations on tree-decomposable graphs
- Parametric problems on graphs of bounded tree-width
- LP formulations for polynomial optimization problems
- Efficient algorithms for solving systems of linear equations and path problems
- Improved Steiner tree algorithms for bounded treewidth
- Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
- The role of Steiner hulls in the solution to Steiner tree problems
- A linear algorithm for the pos/neg-weighted 1-median problem on a cactus
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- On budget-constrained flow improvement.
- New limits of treewidth-based tractability in optimization
- Gainfree Leontief substitution flow problems
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Regularity and locality in \(k\)-terminal graphs
- A linear‐time algorithm for broadcast domination in a tree
- Tree decompositions and social graphs
- The nonexistence of reduction rules giving an embedding into a \(k\)-tree
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Using maximality and minimality conditions to construct inequality chains
- Bicriteria Network Design Problems
- Use of partial substitutions for time decomposition of Boolean functions and generalized graph schemes of algorithms
- Dynamic algorithms for graphs of bounded treewidth
- Tree-edges deletion problems with bounded diameter obstruction sets
- Generalized coloring for tree-like graphs
- Convex dominating sets in maximal outerplanar graphs
- On some complexity properties of N-free posets and posets with bounded decomposition diameter
- Fixed-parameter tractability of treewidth and pathwidth
- On minimum dominating sets with minimum intersection
This page was built for publication: Linear-time computation of optimal subgraphs of decomposable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4728259)
