Parameterized complexity of set-restricted disjoint paths on chordal graphs

DOI10.1007/978-3-031-09574-0_10MaRDI QIDQ2097221zbMATH OpenOpenAlexFDO

Authors 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

chordal graphsdisjoint pathsfptkernelset restricted disjoint paths

Mathematics Subject Classification ID

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

Cites work

• An exponential time parameterized algorithm for planar disjoint paths
• Detecting fixed patterns in chordal graphs in polynomial time
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors. XIII: The disjoint paths problem
• Hitting topological minors is FPT
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Irrelevant vertices for the planar disjoint paths problem
• Kernelization Lower Bounds by Cross-Composition
• Kernelization. Theory of parameterized preprocessing
• Parameterized algorithms
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The \(k\)-disjoint paths problem on chordal graphs
• Well-partitioned chordal graphs: obstruction set and disjoint paths

Cited in

(6)

• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Efficient algorithms for minimal disjoint path problems on chordal graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097221)