A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
From MaRDI portal
Publication:5691297
DOI10.1137/S0097539793251219zbMath0864.68074WikidataQ56141692 ScholiaQ56141692MaRDI QIDQ5691297
Publication date: 9 June 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision, Unnamed Item, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Recursive conditioning, Hypertree decompositions and tractable queries, Girth and treewidth, All structured programs have small tree width and good register allocation, Efficient Union-Find for planar graphs and other sparse graph classes, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, Treewidth for graphs with small chordality, On interval routing schemes and treewidth, Splitting a graph into disjoint induced paths or cycles., Algorithms for generalized vertex-rankings of partial k-trees, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Algorithms and obstructions for linear-width and related search parameters, An algorithm for the Tutte polynomials of graphs of bounded treewidth, Counting \(H-\)colorings of partial \(k-\)trees, Fixed-parameter complexity in AI and nonmonotonic reasoning, Listing all potential maximal cliques of a graph, An implementation of the iterative proportional fitting procedure by propagation trees., Two feedback problems for graphs with bounded tree-width, Tree decompositions with small cost, Embeddings of \(k\)-connected graphs of pathwidth \(k\), Computing the branchwidth of interval graphs, Querying linguistic treebanks with monadic second-order logic in linear time, Parameterized complexity of vertex colouring, Chordal bipartite graphs of bounded tree- and clique-width, Maximum likelihood bounded tree-width Markov networks, Reduction algorithms for graphs of small treewidth, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, The longest common subsequence problem for sequences with nested arc annotations., The parametrized complexity of knot polynomials, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, A polynomial time algorithm for strong edge coloring of partial \(k\)-trees, An existential locality theorem, Computing crossing numbers in quadratic time, Kernels in planar digraphs, The recognizability of sets of graphs is a robust property, Parameterized computation and complexity: a new approach dealing with NP-hardness
