Linear time algorithms for NP-hard problems restricted to partial k- trees

From MaRDI portal

Publication:1116705

Jump to:navigation, search

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)

zbMATH Keywords

optimization dynamic programming NP-hard problems on graphs linear time algorithms for trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Towards the Graph Minor Theorems for Directed Graphs ⋮ Canonical representations of partial 2-and 3-trees ⋮ Testing superperfection of k-trees ⋮ Parametric problems on graphs of bounded tree-width ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Practical algorithms on partial k-trees with an application to domination-like problems ⋮ Boxicity and treewidth ⋮ Unnamed Item ⋮ Graph decompositions and tree automata in reasoning with uncertainty ⋮ On the Satisfiability of Quantum Circuits of Small Treewidth ⋮ Simultaneously dominating all spanning trees of a graph ⋮ The word problem for free adequate semigroups ⋮ The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Decomposability helps for deciding logics of knowledge and belief ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Packing Edge-Disjoint Odd Eulerian Subgraphs Through Prescribed Vertices in 4-Edge-Connected Graphs ⋮ Vector representations of graphs and distinguishing quantum product states with one-way LOCC ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ A bound on the dissociation number ⋮ All longest cycles in a 2‐connected partial 3‐tree share a common vertex ⋮ Flexibility of triangle‐free planar graphs ⋮ The firebreak problem ⋮ \(K_{6}\) minors in 6-connected graphs of bounded tree-width ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ An Improved Algorithm for Finding Cycles Through Elements ⋮ Parameterized complexity of path set packing ⋮ Limits of random tree-like discrete structures ⋮ Augmenting graphs to minimize the radius ⋮ Tree-Width and Optimization in Bounded Degree Graphs ⋮ Asteroidal triple-free graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Unnamed Item ⋮ A lower bound for treewidth and its consequences ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ Grid induced minor theorem for graphs of small degree ⋮ Unnamed Item ⋮ Bandwidth consecutive multicolorings of graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ The Space Complexity of k-Tree Isomorphism ⋮ APPROXIMATION OF GEODESICS IN METABELIAN GROUPS ⋮ Treewidth and pathwidth of permutation graphs ⋮ Graphs of Separability at Most Two: Structural Characterizations and Their Consequences ⋮ Coloring temporal graphs ⋮ Additive non-approximability of chromatic number in proper minor-closed classes ⋮ PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA ⋮ Topological parameters for time-space tradeoff ⋮ Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees ⋮ Vertex-Bipartition Method for Colouring Minor-Closed Classes of Graphs ⋮ SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS ⋮ The Maximum Independent Set Problem in Planar Graphs ⋮ A note on trees, tables, and algorithms ⋮ Unnamed Item ⋮ The basic algorithm for pseudo-Boolean programming revisited ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ A survey of some network reliability analysis and synthesis results ⋮ Using a hybrid of exact and genetic algorithms to design survivable networks ⋮ Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor ⋮ Two strikes against perfect phylogeny ⋮ Completely independent spanning trees in (partial) \(k\)-trees ⋮ Optimization and Recognition for K 5-minor Free Graphs in Linear Time ⋮ Graph minor theory ⋮ Walking through waypoints ⋮ An Efficient Partitioning Oracle for Bounded-Treewidth Graphs ⋮ Faster Computation of Path-Width ⋮ Exact algorithms for a discrete metric labeling problem ⋮ Power Indices in Spanning Connectivity Games ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Convex dominating sets in maximal outerplanar graphs ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ Graph limits of random graphs from a subset of connected k‐trees ⋮ Comparing linear width parameters for directed graphs ⋮ Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs ⋮ Tree decompositions and social graphs ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable ⋮ Critical elements in combinatorially closed families of graph classes ⋮ 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 ⋮ Postman problems on series-parallel mixed graphs ⋮ 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

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1116705&oldid=13160305"