Linear time algorithms for NP-hard problems restricted to partial k- trees
From MaRDI portal
DOI10.1016/0166-218X(89)90031-0zbMATH Open0666.68067WikidataQ56141684 ScholiaQ56141684MaRDI QIDQ1116705FDOQ1116705
Authors: Stefan Arnborg, Andrzej Proskurowski 
Publication date: 1989
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Complement reducible graphs
- Complexity of Finding Embeddings in a k-Tree
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph minors. II. Algorithmic aspects of tree-width
- Triangulated graphs and the elimination process
- Characterization and Recognition of Partial 3-Trees
- 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
- Title not available (Why is that?)
- Computing the Reliability of Complex Networks
- Title not available (Why is that?)
- Linear-time computation of optimal subgraphs of decomposable graphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- Contribution to nonserial dynamic programming
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Title not available (Why is that?)
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
Cited In (only showing first 100 items - show all)
- Traveling salesman problem under categorization
- An efficient partitioning oracle for bounded-treewidth graphs
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- Vertex coloring of graphs with few obstructions
- Graphs without large apples and the maximum weight independent set problem
- Edge-disjoint odd cycles in 4-edge-connected graphs
- The Maximum Independent Set Problem in Planar Graphs
- SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS
- \(k\)-NLC graphs and polynomial algorithms
- The disjoint paths problem in quadratic time
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Graphs of separability at most 2
- Tree-width of hypergraphs and surface duality
- On switching classes, NLC-width, cliquewidth and treewidth
- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Linear connectivity forces large complete bipartite minors
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- Topological parameters for time-space tradeoff
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Outer 1-planar graphs
- A survey of very large-scale neighborhood search techniques
- Title not available (Why is that?)
- Practical algorithms on partial k-trees with an application to domination-like problems
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- An asymptotic analysis of labeled and unlabeled \(k\)-trees
- Power Indices in Spanning Connectivity Games
- Directed tree-width
- On some optimization problems on \(k\)-trees and partial \(k\)-trees
- Clique polynomials and independent set polynomials of graphs
- Graphs of separability at most two: structural characterizations and their consequences
- Dominating sets in perfect graphs
- Asteroidal triple-free graphs
- The Steiner tree polytope and related polyhedra
- Coloring immersion-free graphs
- Treewidth computations. I: Upper bounds
- Title not available (Why is that?)
- Subexponential parameterized algorithms
- Title not available (Why is that?)
- Coloring graphs characterized by a forbidden subgraph
- The struction algorithm for the maximum stable set problem revisited
- Triangulating multitolerance graphs
- Listing all potential maximal cliques of a graph
- Parametric problems on graphs of bounded tree-width
- Completely independent spanning trees in (partial) \(k\)-trees
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Title not available (Why is that?)
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- Parameterized complexity of vertex colouring
- The basic algorithm for pseudo-Boolean programming revisited
- The parameterised complexity of list problems on graphs of bounded treewidth
- Characterizing width two for variants of treewidth
- Computing residual connectedness reliability for restricted networks
- On shortest disjoint paths in planar graphs
- How to compute digraph width measures on directed co-graphs
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Open Problems on Graph Coloring for Special Graph Classes
- A spectral lower bound for the treewidth of a graph and its consequences
- All structured programs have small tree width and good register allocation
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- Regularity and locality in \(k\)-terminal graphs
- Complexity of Finding Embeddings in a k-Tree
- Boxicity and treewidth
- Tree-Width and Optimization in Bounded Degree Graphs
- Girth and treewidth
- Augmenting graphs to minimize the radius
- Toughness, hamiltonicity and split graphs
- Network construction/restoration problems: cycles and complexity
- Graph minor theory
- Generalized coloring for tree-like graphs
- The Space Complexity of k-Tree Isomorphism
- Fixed-parameter tractability of treewidth and pathwidth
- Two strikes against perfect phylogeny
- List matrix partitions of chordal graphs
- Efficient sets in partial \(k\)-trees
- Local and global relational consistency
- Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
- Limits of random tree-like discrete structures
- 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
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
- Title not available (Why is that?)
- Complexity of path-forming games
- On the structure of contractible edges in \(k\)-connected partial \(k\)-trees
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA
- Canonical representations of partial 2- and 3-trees
- Efficient frequent connected subgraph mining in graphs of bounded tree-width
- Title not available (Why is that?)
- The isomorphism problem for \(k\)-trees is complete for logspace
- Conversion of coloring algorithms into maximum weight independent set algorithms
- The word problem for free adequate semigroups
- A survey of some network reliability analysis and synthesis results
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
This page was built for publication: Linear time algorithms for NP-hard problems restricted to partial k- trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116705)
