Finding disjoint paths in split graphs

DOI10.1007/S00224-014-9580-6MaRDI QIDQ493652zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Pim Van 't Hof, Erik Jan van Leeuwen, Reza Saei

Publication date 4 September 2015

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-014-9580-6

zbMATH Keywords

computational complexityparameterized complexitypolynomial kerneldisjoint pathssplit graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Finding disjoint paths in split graphs
• Kernelization of two path searching problems on split graphs
• On the kernelization of split graph problems
• Kernel bounds for disjoint cycles and disjoint paths
• Graph minors. XIII: The disjoint paths problem

Cites work

• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 7051285 (Why is no real title available?)
• scientific article; zbMATH DE number 7051288 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• (Meta) Kernelization
• A simplified NP-complete satisfiability problem
• Algorithmic graph theory and perfect graphs
• Finding disjoint paths in split graphs
• Graph minors. XIII: The disjoint paths problem
• Kernel bounds for disjoint cycles and disjoint paths
• NP-completeness of some edge-disjoint paths problems
• On problems without polynomial kernels
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• The \(k\)-disjoint paths problem on chordal graphs
• The disjoint paths problem in quadratic time
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• The splittance of a graph
• Vertex disjoint paths on clique-width bounded graphs

Cited in

(11)

• Finding disjoint paths in split graphs
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Kernelization of two path searching problems on split graphs
• Finding disjoint paths with related path costs
• On the kernelization of split graph problems
• Finding multiple induced disjoint paths in general graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Disjoint paths and connected subgraphs for \(H\)-free graphs
• Splitting a graph into disjoint induced paths or cycles.
• scientific article; zbMATH DE number 1439419 (Why is no real title available?)
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage

This page was built for publication: Finding disjoint paths in split graphs

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