19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

A Boundary Class for the k-Path Partition Problem

Presented by Mr. Nicholas KORPELAINEN
Type: Oral presentation
Track: Algorithmic Graph Theory


The k-path partition problem, i.e. finding the minimum number of paths of length at most k that partition a graph, is an algorithmic graph problem with many real-life applications, such as in route design or communication networks. We will discuss the complexity status of this problem for various hereditary graph classes. The concept of 'boundary classes' will be introduced -- these are defined as a workaround to the problem of defining a 'minimal' class within a family of (possibly infinite) classes. We find the first boundary class for the family of graph classes for which the k-path partition problem is NP-hard.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors