Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

Related Items (only showing first 100 items - show all)

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

This page was built for publication: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs