Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parameterized Maximum Path Coloring
2011 (English)Conference paper, Published 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
2011.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-58575OAI: oai:DiVA.org:kth-58575DiVA: diva2:473377
Conference
IPEC 2011, The Sixth International Symposium on Parameterized and Exact Computation. Saarbr├╝cken, Germany, September 7-9, 2011
Note
QC 20120113 Available from: 2012-02-06 Created: 2012-01-05 Last updated: 2012-02-06Bibliographically approved

Open Access in DiVA

fulltext(323 kB)47 downloads
File information
File name FULLTEXT01.pdfFile size 323 kBChecksum SHA-512
66f51b070a9a2c31d4ca693c6ad98b9fcc62690890ad93813a1d769a44726d5ec6334ff7adff65e545b805ac271972f1c8659115a83470f75b4bb1e1c23e53ef
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: 47 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

urn-nbn

Altmetric score

urn-nbn
Total: 69 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf