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, The Valve Location Problem in Simple Network Topologies, Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Heuristic and metaheuristic methods for computing graph treewidth, Unnamed Item, An algorithm for simultaneous backbone threading and side-chain packing, 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, Equitable colorings of bounded treewidth graphs, Safe separators for treewidth, Compatibility of unrooted phylogenetic trees is FPT, Trees, grids, and MSO decidability: from graphs to matroids, Online promise problems with online width metrics, Some recent progress and applications in graph minor theory, Achievable sets, brambles, and sparse treewidth obstructions, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Treewidth lower bounds with brambles, Maximum \(k\)-splittable \(s, t\)-flows, Three-connected graphs whose maximum nullity is at most three, An annotated bibliography on guaranteed graph searching, On the parameterized complexity of layered graph drawing, Some tractable instances of interval data minmax regret problems, Treewidth and logical definability of graph products, A spectral lower bound for the treewidth of a graph and its consequences, Derivation of algorithms for cutwidth and related graph layout parameters, 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, Degree-constrained decompositions of graphs: Bounded treewidth and planarity, Tree-decompositions with bags of small diameter, Efficient algorithms for center problems in cactus networks, Spanners for bounded tree-length graphs, Algorithms for finding distance-edge-colorings of graphs, Case-factor diagrams for structured probabilistic modeling, Visualizing SAT instances and runs of the DPLL algorithm, Tree decomposition and discrete optimization problems: a survey, Planar graph bipartization in linear time, Kernels in planar digraphs, An exact method for graph coloring, On the colored Tutte polynomial of a graph of bounded treewidth, Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees, Improved bottleneck domination algorithms, The recognizability of sets of graphs is a robust property, Parameterized computation and complexity: a new approach dealing with NP-hardness, Boxicity and treewidth, The relative clique-width of a graph, Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs, Graph decompositions for cartesian products, Algorithms for Propositional Model Counting, An Improved Algorithm for Finding Cycles Through Elements, Efficient First-Order Model-Checking Using Short Labels, Obtaining a Planar Graph by Vertex Deletion, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Monadic Second Order Logic on Graphs with Local Cardinality Constraints, Equitable list coloring and treewidth
