The Pathwidth and Treewidth of Cographs
From MaRDI portal
Recommendations
Cited in
(83)- Approximating the maximum clique minor and some subgraph homeomorphism problems
- An optimal parallel algorithm for node ranking of cographs
- A partial k-arboretum of graphs with bounded treewidth
- Triangulating graphs with few \(P_4\)'s
- Partial and perfect path covers of cographs
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Treewidth for graphs with small chordality
- Characterizations and algorithmic applications of chordal graph embeddings
- On interval routing schemes and treewidth
- Fugitive-search games on graphs and related parameters
- Triangulating multitolerance graphs
- Edge and node searching problems on trees
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Tree decompositions with small cost
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Directed path-width and directed tree-width of directed co-graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Triangulating graphs without asteroidal triples
- On characterizations for subclasses of directed co-graphs
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- How to compute digraph width measures on directed co-graphs
- On the spectrum and number of convex sets in graphs
- A revisit of the scheme for computing treewidth and minimum fill-in
- Node-searching problem on block graphs
- Linear layouts measuring neighbourhoods in graphs
- Efficient parallel recognition of cographs
- Finding a maximum minimal separator: graph classes and fixed-parameter tractability
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Treewidth and Pathwidth Parameterized by the Vertex Cover Number
- Fixed-parameter tractability of treewidth and pathwidth
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Computing directed pathwidth in O(1.89ⁿ) time
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Linear-time algorithm for the matched-domination problem in cographs
- scientific article; zbMATH DE number 4173000 (Why is no real title available?)
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- On some simple widths
- Treewidth and pathwidth parameterized by the vertex cover number
- A Characterisation of the Minimal Triangulations of Permutation Graphs
- Pathwidth of Circular-Arc Graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Inference and Learning in Multi-dimensional Bayesian Network Classifiers
- Two characterisations of the minimal triangulations of permutation graphs
- Weighted maximum-clique transversal sets of graphs
- Edge search number of cographs
- Automata-based Representations for Infinite Graphs
- How to use the minimal separators of a graph for its chordal triangulation
- Treewidth and Pathwidth of Permutation Graphs
- Linear-time constant-ratio approximation algorithm and tight bounds for the contiguity of cographs
- The complexity of minimum-length path decompositions
- \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
- On perfect and quasiperfect dominations in graphs
- Neighbourhood-width of trees
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- The pathwidth and treewidth of cographs
- Comparing the metric and strong dimensions of graphs
- Bounding the search number of graph products
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Edge Search Number of Cographs in Linear Time
- Tree decompositions and social graphs
- Tree-decompositions of small pathwidth
- Computing subset transversals in \(H\)-free graphs
- On intervalizing k-colored graphs for DNA physical mapping
- Principled deep neural network training through linear programming
- On Interval Routing Schemes and treewidth
- Treewidth versus clique number. II: Tree-independence number
- Tree-width and path-width of comparability graphs of interval orders
- Fugitive-search games on graphs and related parameters
- Acyclic and star colorings of cographs
- Graph searching on chordal graphs
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- The complexity of subgraph isomorphism for classes of partial k-trees
- Treewidth and minimum fill-in on permutation graphs in linear time
- Covering and partitioning of split, chain and cographs with isometric paths
- Covering and partitioning of split, chain and cographs with isometric paths
- Exclusive graph searching vs. pathwidth
- A vertex incremental approach for maintaining chordality
- The micro-world of cographs
- Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
- Treewidth computations. I: Upper bounds
- Dynamic programming and planarity: improved tree-decomposition based algorithms
This page was built for publication: The Pathwidth and Treewidth of Cographs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4695381)