Finding small-width connected path decompositions in polynomial time
From MaRDI portal
Publication:2328867
DOI10.1016/j.tcs.2019.03.039zbMath1431.68090arXiv1802.05501MaRDI QIDQ2328867
Dorota Osula, Dariusz Dereniowski, Paweł Rzążewski
Publication date: 16 October 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.05501
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C40: Connectivity
Related Items
A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Unnamed Item, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
Cites Work
- Unnamed Item
- Contraction obstructions for connected graph searching
- The complexity of minimum-length path decompositions
- Mixed searching and proper-path-width
- Connected graph searching
- A note on exact algorithms for vertex ordering problems on graphs
- Graph minors. XX: Wagner's conjecture
- Connected searching of weighted trees
- Approximation algorithms for treewidth
- An annotated bibliography on guaranteed graph searching
- Distributed chasing of network intruders
- Connected graph searching in chordal graphs
- Monotony properties of connected visible graph searching
- Graph searching with advice
- Sweeping graphs with large clique number
- Graph minors. I. Excluding a forest
- The vertex separation and search number of a graph
- Searching and pebbling
- Distributed graph searching with a sense of direction
- The cost of monotonicity in distributed graph searching
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Faster Computation of Path-Width
- Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings
- Connected Graph Searching in Outerplanar Graphs
- Connected Treewidth and Connected Graph Searching
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Computing Pathwidth Faster Than 2 n
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Computing Directed Pathwidth in O(1.89 n ) Time
- From Pathwidth to Connected Pathwidth
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
