A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth

DOI10.1137/20M1369361zbMath1485.05172arXiv2004.11937MaRDI QIDQ5062107

Christophe Paul, Mamadou Moustapha Kanté, Dimitrios M. Thilikos

Publication date: 15 March 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.11937

zbMATH Keywords

graph decompositionparameterized algorithmscops and robber gamewidth parameter

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ Edge-treewidth: algorithmic and combinatorial properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Connected graph searching
• Graph minors. XX: Wagner's conjecture
• A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
• An annotated bibliography on guaranteed graph searching
• Derivation of algorithms for cutwidth and related graph layout parameters
• Sweeping graphs with large clique number
• Graph minors. I. Excluding a forest
• Interval graphs and searching
• Quickly excluding a forest
• The vertex separation number of a graph equals its path-width
• Upper bounds on the size of obstructions and intertwines
• On the monotonicity of games generated by symmetric submodular functions.
• Searching and pebbling
• Finding small-width connected path decompositions in polynomial time
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Faster Computation of Path-Width
• Complexity of Finding Embeddings in a k-Tree
• Monotonicity in graph searching
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• Constructive linear time algorithms for branchwidth
• Constructive algorithm for path-width of matroids
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• From Pathwidth to Connected Pathwidth
• Finding branch-decompositions of matroids, hypergraphs, and more
• Parameterized and Exact Computation
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Graph-Theoretic Concepts in Computer Science
• Tree-decompositions of small pathwidth
• Connected search for a lazy robber

This page was built for publication: A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth