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)
- 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
- Minimum self-repairing graphs
- A lower bound for treewidth and its consequences
- Nonempty intersection of longest paths in series-parallel graphs
- Tutte polynomials computable in polynomial time
- Comparing linear width parameters for directed graphs
- Title not available (Why is that?)
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Some recent progress and applications in graph minor theory
- An Improved Algorithm for Finding Cycles Through Elements
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- On the complexity of the regenerator location problem treewidth and other parameters
- Well-quasi-orders in subclasses of bounded treewidth graphs
- Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
- Parameterized complexity of path set packing
- Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Treewidth and pathwidth of permutation graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the max min vertex cover problem
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- Algorithms for finding an induced cycle in planar graphs
- Tree decompositions and social graphs
- A Logspace Algorithm for Partial 2-Tree Canonization
- A new graph construction of unbounded clique-width
- Convex dominating sets in maximal outerplanar graphs
- Flexibility of triangle‐free planar graphs
- Bandwidth consecutive multicolorings of graphs
- Hardness of computing clique number and chromatic number for Cayley graphs
- The behavior of clique-width under graph operations and graph transformations
- On the queue-number of graphs with bounded tree-width
- Random enriched trees with applications to random graphs
- Partitioning graphs of supply and demand
- On minimum dominating sets with minimum intersection
- A simple linear-time algorithm for finding path-decompositions of small width
- Peptide sequencing via graph path decomposition
- 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
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)
