Linear time algorithms for NP-hard problems restricted to partial k- trees
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3917707 (Why is no real title available?)
- scientific article; zbMATH DE number 3956440 (Why is no real title available?)
- scientific article; zbMATH DE number 3974289 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Characterization and Recognition of Partial 3-Trees
- Complement reducible graphs
- Complexity of Finding Embeddings in a k-Tree
- Computing the Reliability of Complex Networks
- Contribution to nonserial dynamic programming
- Dynamic Programming is Optimal for Nonserial Optimization Problems
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph minors. II. Algorithmic aspects of tree-width
- Linear-time computability of combinatorial problems on series-parallel graphs
- Linear-time computation of optimal subgraphs of decomposable graphs
- Reduced State EnumerationߞAnother Algorithm for Reliability Evaluation
- The NP-completeness column: An ongoing guide
- Triangulated graphs and the elimination process
Cited in
(only showing first 100 items - show all)- The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- \(k\)-NLC graphs and polynomial algorithms
- Two strikes against perfect phylogeny
- Edge-disjoint odd cycles in 4-edge-connected graphs
- Graph minor theory
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Generalized coloring for tree-like graphs
- Traveling salesman problem under categorization
- The disjoint paths problem in quadratic time
- The parameterised complexity of list problems on graphs of bounded treewidth
- Characterizing width two for variants of treewidth
- The basic algorithm for pseudo-Boolean programming revisited
- Augmenting graphs to minimize the radius
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Graphs of separability at most two: structural characterizations and their consequences
- Practical algorithms on partial k-trees with an application to domination-like problems
- On some optimization problems on \(k\)-trees and partial \(k\)-trees
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Power Indices in Spanning Connectivity Games
- Clique polynomials and independent set polynomials of graphs
- A survey of very large-scale neighborhood search techniques
- Graphs of separability at most 2
- Tree-width of hypergraphs and surface duality
- On switching classes, NLC-width, cliquewidth and treewidth
- \(K_{6}\) minors in 6-connected graphs of bounded tree-width
- Toughness, hamiltonicity and split graphs
- Listing all potential maximal cliques of a graph
- Treewidth computations. I: Upper bounds
- The Steiner tree polytope and related polyhedra
- Directed tree-width
- Parameterized dominating set problem in chordal graphs: Complexity and lower bound
- Network construction/restoration problems: cycles and complexity
- Computing residual connectedness reliability for restricted networks
- Dominating sets in perfect graphs
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- A spectral lower bound for the treewidth of a graph and its consequences
- All structured programs have small tree width and good register allocation
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Parametric problems on graphs of bounded tree-width
- Completely independent spanning trees in (partial) \(k\)-trees
- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- The struction algorithm for the maximum stable set problem revisited
- Vertex coloring of graphs with few obstructions
- An efficient partitioning oracle for bounded-treewidth graphs
- List-coloring graphs without subdivisions and without immersions
- How to compute digraph width measures on directed co-graphs
- The Maximum Independent Set Problem in Planar Graphs
- Boxicity and treewidth
- List matrix partitions of chordal graphs
- Linear connectivity forces large complete bipartite minors
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS
- Linear-programming design and analysis of fast algorithms for Max 2-CSP
- An asymptotic analysis of labeled and unlabeled \(k\)-trees
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- Regularity and locality in \(k\)-terminal graphs
- Open problems on graph coloring for special graph classes
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- Asteroidal triple-free graphs
- The Space Complexity of k-Tree Isomorphism
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Fixed-parameter tractability of treewidth and pathwidth
- On shortest disjoint paths in planar graphs
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Coloring immersion-free graphs
- scientific article; zbMATH DE number 3917707 (Why is no real title available?)
- Subexponential parameterized algorithms
- Triangulating multitolerance graphs
- Tree-Width and Optimization in Bounded Degree Graphs
- Graphs without large apples and the maximum weight independent set problem
- Complexity of Finding Embeddings in a k-Tree
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- Outer 1-planar graphs
- Girth and treewidth
- Coloring graphs characterized by a forbidden subgraph
- Parameterized complexity of vertex colouring
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Topological parameters for time-space tradeoff
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- Complexity of path-forming games
- Partitioning graphs of supply and demand
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- On minimum dominating sets with minimum intersection
- A Logspace Algorithm for Partial 2-Tree Canonization
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Parameterized complexity of path set packing
- Flexibility of triangle‐free planar graphs
- scientific article; zbMATH DE number 3878376 (Why is no real title available?)
- Tree decompositions and social 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
- scientific article; zbMATH DE number 4024784 (Why is no real title available?)
- Efficient frequent connected subgraph mining in graphs of bounded tree-width
- Faster approximation schemes and parameterized algorithms on (odd-)\(H\)-minor-free graphs
- A lower bound for treewidth and its consequences
- An Improved Algorithm for Finding Cycles Through Elements
- scientific article; zbMATH DE number 4174333 (Why is no real title available?)
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
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)
