The complexity of minimum-length path decompositions
From MaRDI portal
Publication:494076
DOI10.1016/j.jcss.2015.06.011zbMath1328.68088arXiv1302.2788OpenAlexW2763773774MaRDI QIDQ494076
Yori Zwols, Dariusz Dereniowski, Wiesław X. Kubiak
Publication date: 31 August 2015
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1302.2788
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Minimum size tree-decompositions ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Finding small-width connected path decompositions in polynomial time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of subgraph isomorphism for classes of partial k-trees
- An annotated bibliography on guaranteed graph searching
- Graph minors. I. Excluding a forest
- Interval graphs and searching
- Narrowness, pathwidth, and their application in natural language processing
- The vertex separation number of a graph equals its path-width
- A partial k-arboretum of graphs with bounded treewidth
- On the pathwidth of chordal graphs
- The vertex separation and search number of a graph
- Treewidth. Computations and approximations
- Fugitive-search games on graphs and related parameters
- Helicopter search problems, bandwidth and pathwidth
- Step-wise tile assembly with a constant number of tile types
- Graph searching, elimination trees, and a generalization of bandwidth
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Searching and pebbling
- Graph Searching and Interval Completion
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Complexity of Finding Embeddings in a k-Tree
- Monotonicity in graph searching
- Complete Register Allocation Problems
- The Pathwidth and Treewidth of Cographs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- From Pathwidth to Connected Pathwidth
- Treewidth: Structure and Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- SOFSEM 2006: Theory and Practice of Computer Science
This page was built for publication: The complexity of minimum-length path decompositions
