On the pathwidth of chordal graphs
From MaRDI portal
Publication:1309811
DOI10.1016/0166-218X(93)90012-DzbMATH Open0798.68134DBLPjournals/dam/Gustedt93WikidataQ29305659 ScholiaQ29305659MaRDI QIDQ1309811FDOQ1309811
Authors: Jens Gustedt 
Publication date: 31 October 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Title not available (Why is that?)
- Min Cut is NP-complete for edge weighted trees
- Searching and pebbling
- Easy problems for tree-decomposable graphs
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Graph minors. II. Algorithmic aspects of tree-width
- A Characterization of Comparability Graphs and of Interval Graphs
- The complexity of searching a graph
- Graph minors. I. Excluding a forest
- Interval graphs and searching
- The pathwidth and treewidth of cographs
- Title not available (Why is that?)
- A characterisation of rigid circuit graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The NP-completeness column: An ongoing guide
Cited In (42)
- Pathwidth of Circular-Arc Graphs
- Non-deterministic graph searching in trees
- Approximating Pathwidth for Graphs of Small Treewidth
- Pursuing a fast robber on a graph
- Connected graph searching in chordal graphs
- Minimal interval completion through graph exploration
- Edge Search Number of Cographs in Linear Time
- On tradeoffs between width- and fill-like graph parameters
- Edge search number of cographs
- On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
- Dominoes
- Treewidth for graphs with small chordality
- Corrigendum to: ``On the monophonic rank of a graph
- Computing directed pathwidth in \(O(1.89^n)\) time
- Triangulating graphs without asteroidal triples
- Characterizations and directed path-width of sequence digraphs
- Complexity of approximating the oriented diameter of chordal graphs
- Approximate search strategies for weighted trees
- Vertex deletion problems on chordal graphs
- Well-partitioned chordal graphs
- Edge and node searching problems on trees
- The complexity of zero-visibility cops and robber
- Three-fast-searchable graphs
- Multicore graphs: characterization and properties
- On the interval completion of chordal graphs
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Vertex deletion problems on chordal graphs
- Variable neighborhood search for the vertex separation problem
- Decision Diagram Decomposition for Quadratically Constrained Binary Optimization
- Mixed search number and linear-width of interval and split graphs
- Node-searching problem on block graphs
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- How to compute digraph width measures on directed co-graphs
- Treewidth and pathwidth of permutation graphs
- The complexity of minimum-length path decompositions
- Mixed Search Number of Permutation Graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Graph searching on chordal graphs
- On the monophonic rank of a graph
- Homotopy height, grid-major height and graph-drawing height
- Pathwidth is NP-Hard for Weighted Trees
- Exclusive graph searching vs. pathwidth
This page was built for publication: On the pathwidth of chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1309811)
