Linear time algorithms for NP-hard problems restricted to partial k- trees
From MaRDI portal
Publication:1116705
DOI10.1016/0166-218X(89)90031-0zbMath0666.68067WikidataQ56141684 ScholiaQ56141684MaRDI QIDQ1116705
Andrzej Proskurowski, Stefan Arnborg
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (only showing first 100 items - show all)
Arborescence polytopes for series-parallel graphs ⋮ Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ A review of combinatorial problems arising in feedforward neural network design ⋮ The struction algorithm for the maximum stable set problem revisited ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ Regularity and locality in \(k\)-terminal graphs ⋮ Outer 1-planar graphs ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees ⋮ Reliability analysis of a simple replicated and-fork/and-join graph ⋮ Parameterized dominating set problem in chordal graphs: Complexity and lower bound ⋮ An asymptotic analysis of labeled and unlabeled \(k\)-trees ⋮ On the structure of contractible edges in \(k\)-connected partial \(k\)-trees ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ Linear-time algorithms for problems on planar graphs with fixed disk dimension ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Coloring immersion-free graphs ⋮ Generalized coloring for tree-like graphs ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Characterizing width two for variants of treewidth ⋮ Vertex coloring of graphs with few obstructions ⋮ Random enriched trees with applications to random graphs ⋮ Network construction/restoration problems: cycles and complexity ⋮ Toughness, hamiltonicity and split graphs ⋮ Minimum self-repairing graphs ⋮ Exploiting sparsity for the min \(k\)-partition problem ⋮ Some recent progress and applications in graph minor theory ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ Local and global relational consistency ⋮ Triangulating multitolerance graphs ⋮ On the complexity of the regenerator location problem treewidth and other parameters ⋮ The disjoint paths problem in quadratic time ⋮ Tree-width of hypergraphs and surface duality ⋮ Graphs of separability at most 2 ⋮ On switching classes, NLC-width, cliquewidth and treewidth ⋮ On shortest disjoint paths in planar graphs ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ Subexponential parameterized algorithms ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Maximum packing for biconnected outerplanar graphs ⋮ Algorithms for finding an induced cycle in planar graphs ⋮ Dominating sets in perfect graphs ⋮ On minimum dominating sets with minimum intersection ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ On the max min vertex cover problem ⋮ A new graph construction of unbounded clique-width ⋮ Canonical representations of partial 2- and 3-trees ⋮ Hardness of computing clique number and chromatic number for Cayley graphs ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Efficient sets in partial \(k\)-trees ⋮ Computing residual connectedness reliability for restricted networks ⋮ Tutte polynomials computable in polynomial time ⋮ On the queue-number of graphs with bounded tree-width ⋮ Traveling salesman problem under categorization ⋮ On the complexity of finding iso- and other morphisms for partial \(k\)- trees ⋮ Peptide sequencing via graph path decomposition ⋮ Treewidth computations. I: Upper bounds ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Partitioning graphs of supply and demand ⋮ Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm ⋮ A survey of very large-scale neighborhood search techniques ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Complexity of path-forming games ⋮ Two feedback problems for graphs with bounded tree-width ⋮ Efficiently parallelizable problems on a class of decomposable graphs ⋮ Connectivity of the graph induced by contractible edges of a \(k\)-tree ⋮ Girth and treewidth ⋮ Conversion of coloring algorithms into maximum weight independent set algorithms ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Nonempty intersection of longest paths in series-parallel graphs ⋮ Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ A spectral lower bound for the treewidth of a graph and its consequences ⋮ Parameterized complexity of vertex colouring ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ All structured programs have small tree width and good register allocation ⋮ Linear connectivity forces large complete bipartite minors ⋮ Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs ⋮ Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth ⋮ An algorithm for the Tutte polynomials of graphs of bounded treewidth ⋮ Revising Johnson's table for the 21st century ⋮ Directed tree-width ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ On some optimization problems on \(k\)-trees and partial \(k\)-trees ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Listing all potential maximal cliques of a graph ⋮ Clique polynomials and independent set polynomials of graphs ⋮ The Steiner tree polytope and related polyhedra ⋮ List matrix partitions of chordal graphs ⋮ Towards the Graph Minor Theorems for Directed Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Complement reducible graphs
- Contribution to nonserial dynamic programming
- Triangulated graphs and the elimination process
- Characterization and Recognition of Partial 3-Trees
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- Linear-time computability of combinatorial problems on series-parallel graphs
- Computing the Reliability of Complex Networks
- Linear-time computation of optimal subgraphs of decomposable graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The NP-completeness column: An ongoing guide
This page was built for publication: Linear time algorithms for NP-hard problems restricted to partial k- trees
