Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
From MaRDI portal
Publication:4895809
DOI10.1006/jagm.1996.0049zbMath0861.68036OpenAlexW2125058377WikidataQ29396868 ScholiaQ29396868MaRDI QIDQ4895809
Publication date: 11 May 1997
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://dspace.library.uu.nl/handle/1874/21989
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Treelength of series-parallel graphs, Edge-treewidth: algorithmic and combinatorial properties, Approximating Pathwidth for Graphs of Small Treewidth, On the complexity of the storyplan problem, On the complexity of the storyplan problem, Solving infinite-domain CSPs using the patchwork property, A Modern View on Stability of Approximation, On the parameterized complexity of s-club cluster deletion problems, On the parameterized complexity of \(s\)-club cluster deletion problems, Recognizing map graphs of bounded treewidth, On integer linear programs for treewidth based on perfect elimination orderings, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Faster graph coloring in polynomial space, Complexity and monotonicity results for domination games, The parametrized complexity of knot polynomials, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, As Time Goes By: Reflections on Treewidth for Temporal Graphs, Computing Tree Decompositions, I/O-efficient algorithms for graphs of bounded treewidth, Approximating the pathwidth of outerplanar graphs, Linear-time algorithms for problems on planar graphs with fixed disk dimension, Constraint satisfaction with bounded treewidth revisited, A Basic Parameterized Complexity Primer, Fixed-Parameter Tractability of Treewidth and Pathwidth, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, On the complexity of rainbow coloring problems, Unnamed Item, Unnamed Item, Kernelization using structural parameters on sparse graph classes, Online promise problems with online width metrics, Characterizing width two for variants of treewidth, Symbolic techniques in satisfiability solving, On Compiling Structured CNFs to OBDDs, Pathwidth is NP-Hard for Weighted Trees, Treewidth for graphs with small chordality, Computing the vertex separation of unicyclic graphs, A Simpler Self-reduction Algorithm for Matroid Path-Width, Constructive linear time algorithms for branchwidth, Finding branch-decompositions of matroids, hypergraphs, and more, On compiling structured CNFs to OBDDs, Finite Integer Index of Pathwidth and Treewidth, Approximate search strategies for weighted trees, Solving projected model counting by utilizing treewidth and its limits, The complexity of minimum convex coloring, Pathwidth of Circular-Arc Graphs, Unnamed Item, An FPT 2-approximation for tree-cut decomposition, Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\), Typical sequences revisited -- computing width parameters of graphs, An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, Imbalance is fixed parameter tractable, Confronting intractability via parameters, Unnamed Item, Cutwidth: obstructions and algorithmic aspects, Computing the pathwidth of directed graphs with small vertex cover, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Excluded Forest Minors and the Erdős–Pósa Property, The complexity of minimum-length path decompositions, Node-searching problem on block graphs, \(k\)-chordal graphs: from cops and robber to compact routing via treewidth, Counting linear extensions: parameterizations by treewidth, The complexity of subgraph isomorphism for classes of partial k-trees, New width parameters for SAT and \#SAT, A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions, Crossing number for graphs with bounded pathwidth, On the complexity of computing treebreadth, A 3-approximation for the pathwidth of Halin graphs, A 3-approximation for the pathwidth of Halin graphs, On the parameterized complexity of layered graph drawing, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, Embeddings of \(k\)-connected graphs of pathwidth \(k\), A graph search algorithm for indoor pursuit/evasion, Linear ordering based MIP formulations for the vertex separation or pathwidth problem, Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2, On structural parameterizations of the edge disjoint paths problem, A $c^k n$ 5-Approximation Algorithm for Treewidth, Measuring what matters: a hybrid approach to dynamic programming with treewidth, A linear edge kernel for two-layer crossing minimization, Strengthening Erdös-Pósa property for minor-closed graph classes, Derivation of algorithms for cutwidth and related graph layout parameters, Faster Computation of Path-Width, Optimal tree decompositions revisited: a simpler linear-time FPT algorithm, Parameterized Complexity Results for 1-safe Petri Nets, Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques, Parameterized Complexity of Discrete Morse Theory, FPT is characterized by useful obstruction sets, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Unnamed Item, Unnamed Item, A Polynomial Time Algorithm for Bounded Directed Pathwidth, Algorithms for generalized vertex-rankings of partial k-trees, Edge and node searching problems on trees, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Finding small-width connected path decompositions in polynomial time, Algorithms and obstructions for linear-width and related search parameters, Unnamed Item, Unnamed Item, Unnamed Item, A faster tree-decomposition based algorithm for counting linear extensions, AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH, Finding Branch-Decompositions of Matroids, Hypergraphs, and More, Non-deterministic graph searching in trees, Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming, Linear rank-width and linear clique-width of trees, Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, Counting \(H-\)colorings of partial \(k-\)trees, Myhill-Nerode Methods for Hypergraphs, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS, Exact algorithms for intervalizing coloured graphs, Equitable colorings of bounded treewidth graphs, List matrix partitions of chordal graphs
