Finding disjoint paths in split graphs

DOI10.1007/S00224-014-9580-6zbMATH Open1329.68142OpenAlexW2084983168MaRDI QIDQ493652FDOQ493652

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

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

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)

Cites Work

• Title not available (Why is that?)
• On problems without polynomial kernels
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• The \(k\)-disjoint paths problem on chordal graphs
• A simplified NP-complete satisfiability problem
• Title not available (Why is that?)
• The disjoint paths problem in quadratic time
• On the Complexity of Timetable and Multicommodity Flow Problems
• (Meta) Kernelization
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• The splittance of a graph
• On the Computational Complexity of Combinatorial Problems
• Kernel bounds for disjoint cycles and disjoint paths
• Title not available (Why is that?)
• NP-completeness of some edge-disjoint paths problems
• Title not available (Why is that?)
• Vertex disjoint paths on clique-width bounded graphs
• Finding disjoint paths in split graphs
• Title not available (Why is that?)

Cited In (11)

• Kernelization of two path searching problems on split graphs
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• On the kernelization of split graph problems
• Splitting a graph into disjoint induced paths or cycles.
• Title not available (Why is that?)
• Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
• Finding disjoint paths with related path costs
• 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
• Finding disjoint paths in split graphs

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)