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)- 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
- A simple linear-time algorithm for finding path-decompositions of small width
- Efficient sets in partial \(k\)-trees
- Some recent progress and applications in graph minor theory
- On the complexity of the regenerator location problem treewidth and other parameters
- Convex dominating sets in maximal outerplanar graphs
- Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Nonempty intersection of longest paths in series-parallel graphs
- Tutte polynomials computable in polynomial time
- The isomorphism problem for \(k\)-trees is complete for logspace
- Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
- The complexity of some graph problems with bounded minors of their constraint matrices
- Comparing linear width parameters for directed graphs
- On the structure of contractible edges in \(k\)-connected partial \(k\)-trees
- Bandwidth consecutive multicolorings of graphs
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- Local and global relational consistency
- A survey of some network reliability analysis and synthesis results
- Hardness of computing clique number and chromatic number for Cayley graphs
- scientific article; zbMATH DE number 4101265 (Why is no real title available?)
- 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
- On the max min vertex cover problem
- scientific article; zbMATH DE number 4094838 (Why is no real title available?)
- The word problem for free adequate semigroups.
- Peptide sequencing via graph path decomposition
- A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
- Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
- A new graph construction of unbounded clique-width
- Algorithms for finding an induced cycle in planar graphs
- Provably shorter regular expressions from finite automata
- Minimum self-repairing graphs
- Conversion of coloring algorithms into maximum weight independent set algorithms
- Well-quasi-orders in subclasses of bounded treewidth graphs
- Treewidth and pathwidth of permutation graphs
- Canonical representations of partial 2- and 3-trees
- Limits of random tree-like discrete structures
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- 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
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)
