Parameterized complexity of set-restricted disjoint paths on chordal graphs

DOI10.1007/978-3-031-09574-0_10OpenAlexW4285124465MaRDI QIDQ2097221

Fahad Panolan, Ashutosh Rai, Saket Saurabh, Petr A. Golovach

Publication date: 11 November 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-09574-0_10

zbMATH Keywords

kernelchordal graphsdisjoint pathsfptset restricted disjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Irrelevant vertices for the planar disjoint paths problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Graph minors. XIII: The disjoint paths problem
• Well-partitioned chordal graphs: obstruction set and disjoint paths
• Detecting fixed patterns in chordal graphs in polynomial time
• Kernelization
• Kernelization Lower Bounds by Cross-Composition
• An exponential time parameterized algorithm for planar disjoint paths
• Hitting topological minors is FPT
• Finding topological subgraphs is fixed-parameter tractable
• Parameterized Algorithms
• The k-Disjoint Paths Problem on Chordal Graphs

This page was built for publication: Parameterized complexity of set-restricted disjoint paths on chordal graphs