On the pathwidth of chordal graphs

DOI10.1016/0166-218X(93)90012-DzbMath0798.68134WikidataQ29305659 ScholiaQ29305659MaRDI QIDQ1309811

Jens Gustedt

Publication date: 31 October 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-hardchordal graphspathwidthstarlike graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (36)

Treewidth of cocomparability graphs and a new order-theoretic parameter ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Well-partitioned chordal graphs ⋮ Variable neighborhood search for the vertex separation problem ⋮ Edge Search Number of Cographs in Linear Time ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Treewidth for graphs with small chordality ⋮ Triangulating graphs without asteroidal triples ⋮ Approximate search strategies for weighted trees ⋮ Characterizations and directed path-width of sequence digraphs ⋮ On the monophonic rank of a graph ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ Mixed Search Number of Permutation Graphs ⋮ The complexity of zero-visibility cops and robber ⋮ Edge search number of cographs ⋮ Mixed Search Number and Linear-Width of Interval and Split Graphs ⋮ Dominoes ⋮ Homotopy height, grid-major height and graph-drawing height ⋮ Three-fast-searchable graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Treewidth and pathwidth of permutation graphs ⋮ The complexity of minimum-length path decompositions ⋮ Node-searching problem on block graphs ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Connected graph searching in chordal graphs ⋮ On the interval completion of chordal graphs ⋮ Pursuing a fast robber on a graph ⋮ Mixed search number and linear-width of interval and split graphs ⋮ Vertex deletion problems on chordal graphs ⋮ Exclusive graph searching vs. pathwidth ⋮ Minimal interval completion through graph exploration ⋮ Edge and node searching problems on trees ⋮ Decision Diagram Decomposition for Quadratically Constrained Binary Optimization ⋮ Non-deterministic graph searching in trees ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Min Cut is NP-complete for edge weighted trees
• Searching and pebbling
• A characterisation of rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• The complexity of searching a graph
• Reducibility among Combinatorial Problems
• The pathwidth and treewidth of cographs
• A Characterization of Comparability Graphs and of Interval Graphs
• The NP-completeness column: An ongoing guide

This page was built for publication: On the pathwidth of chordal graphs