A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
From MaRDI portal
Publication:5691297
DOI10.1137/S0097539793251219zbMath0864.68074OpenAlexW2059372025WikidataQ56141692 ScholiaQ56141692MaRDI QIDQ5691297
Publication date: 9 June 1997
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793251219
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (only showing first 100 items - show all)
Improving robustness of next-hop routing ⋮ Safe separators for treewidth ⋮ Compatibility of unrooted phylogenetic trees is FPT ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification ⋮ Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems ⋮ Outer 1-planar graphs ⋮ Structural parameterizations for boxicity ⋮ Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ A note on multiflows and treewidth ⋮ 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 ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Approximate tree decompositions of planar graphs in linear time ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ Collective tree spanners in graphs with bounded parameters ⋮ Approximation algorithms for treewidth ⋮ Coloring immersion-free graphs ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ Parameterized complexity of the \(k\)-arc Chinese postman problem ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Online promise problems with online width metrics ⋮ The parameterised complexity of list problems on graphs of bounded treewidth ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ Courcelle's theorem for triangulations ⋮ The minimum vulnerability problem on specific graph classes ⋮ Matching interdiction ⋮ Some recent progress and applications in graph minor theory ⋮ Achievable sets, brambles, and sparse treewidth obstructions ⋮ Increasing the minimum degree of a graph by contractions ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Kernel bounds for path and cycle problems ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Parameterized complexity of connected even/odd subgraph problems ⋮ Optimal cuts and partitions in tree metrics in polynomial time ⋮ Optimization problems in dotted interval graphs ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Weighted maximum-clique transversal sets of graphs ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ The disjoint paths problem in quadratic time ⋮ The complexity of two graph orientation problems ⋮ The complexity of minimum convex coloring ⋮ Compact labelings for efficient first-order model-checking ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Linkless and flat embeddings in 3-space ⋮ On shortest disjoint paths in planar graphs ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ Contracting planar graphs to contractions of triangulations ⋮ Acyclic and star colorings of cographs ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ Treewidth governs the complexity of target set selection ⋮ On the complexity of core, kernel, and bargaining set ⋮ Guard games on graphs: keep the intruder out! ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Confronting intractability via parameters ⋮ Algorithms for finding an induced cycle in planar graphs ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Spanners in sparse graphs ⋮ Approximation algorithms for intersection graphs ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Consequence-based and fixed-parameter tractable reasoning in description logics ⋮ The complexity of minimum-length path decompositions ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Squares of low clique number ⋮ Parameterized complexity of critical node cuts ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ MSOL restricted contractibility to planar graphs ⋮ Efficient computation of the characteristic polynomial of a tree and related tasks ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ FPT algorithms for connected feedback vertex set ⋮ Hypertree decompositions and tractable queries ⋮ Treewidth computations. II. Lower bounds ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Girth and treewidth ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Complexity of secure sets ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Finding cactus roots in polynomial time ⋮ Nonempty intersection of longest paths in series-parallel graphs ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ A linear edge kernel for two-layer crossing minimization ⋮ Connecting knowledge compilation classes and width parameters ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ Complexity of abstract argumentation under a claim-centric view ⋮ A faster tree-decomposition based algorithm for counting linear extensions ⋮ Exact algorithms for intervalizing coloured graphs ⋮ Improved approximation for orienting mixed graphs ⋮ Equitable colorings of bounded treewidth graphs
This page was built for publication: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
