Finding disjoint paths in split graphs
type: Item
instance of: scholarly article
title: Finding disjoint paths in split graphs
zbMATH Open document ID: 1329.68142
author: Pinar Heggernes
author: Pim Van 't Hof
author: Erik Jan van Leeuwen
author: Reza Saei
published in: Theory of Computing Systems
publication date: 2015-09-04T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6478533
zbMATH Keywords: disjoint paths
zbMATH Keywords: computational complexity
zbMATH Keywords: parameterized complexity
zbMATH Keywords: polynomial kernel
zbMATH Keywords: split graphs
MaRDI profile type: Publication
full work available at URL: s00224-014-9580-6
OpenAlex ID: W2084983168
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: The edge-disjoint paths problem is NP-complete for series-parallel graphs
cites work: Q5315023
cites work: Q4633932
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Q3972951
cites work: Algorithmic graph theory and perfect graphs
cites work: Vertex disjoint paths on clique-width bounded graphs
cites work: The splittance of a graph
cites work: Finding Disjoint Paths in Split Graphs
cites work: The k-Disjoint Paths Problem on Chordal Graphs
cites work: On the Computational Complexity of Combinatorial Problems
cites work: The disjoint paths problem in quadratic time
cites work: Q4633929
cites work: Q4352948
cites work: Q4273851
cites work: Graph minors. XIII: The disjoint paths problem
cites work: A simplified NP-complete satisfiability problem
cites work: NP-completeness of some edge-disjoint paths problems
DOI: 10.1007/S00224-014-9580-6
description: scientific article; zbMATH DE number 6478533