Change search
ReferencesLink to record
Permanent link

Direct link
Parameterized Maximum Path Coloring
2011 (English)Conference paper (Refereed)
Abstract [en]

We study the well-known Max Path Coloring problem from a parameterized point of view, focusing on trees and low-treewidth networks. We observe the existence of a variety of reasonable parameters for the problem, such as the maximum degree and treewidth of the net- work graph, the number of available colors and the number of requests one seeks to satisfy or reject. In an eort to understand the impact of each of these parameters on the problem's complexity we study various pa- rameterized versions of the problem deriving xed-parameter tractability and hardness results both for undirected and bi-directed graphs

Place, publisher, year, edition, pages
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-58575OAI: diva2:473377
IPEC 2011, The Sixth International Symposium on Parameterized and Exact Computation. Saarbr├╝cken, Germany, September 7-9, 2011
QC 20120113 Available from: 2012-02-06 Created: 2012-01-05 Last updated: 2012-02-06Bibliographically approved

Open Access in DiVA

fulltext(323 kB)17 downloads
File information
File name FULLTEXT01.pdfFile size 323 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Conference website

Search in DiVA

By author/editor
Michael, Lampis
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 17 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 18 hits
ReferencesLink to record
Permanent link

Direct link