@inproceedings{034b343c9af84d51b134c0bd404c279c,
title = "A linear algorithm for edge-coloring partial k-trees",
abstract = "Many combinatorial problems can be efficiently solved for partial k-trees. The edge-coloring problem is one of a few combinatorial problems for which no linear-time algorithm has been obtained for partial k-trees. The best known algorithm solves the problem for partial k-trees G in time O(nΔ 22(k+1) where n is the number of vertices and Δ is the maximum degree of G. This paper gives a linear algorithm which optimally edge-colors a given partial k-tree for fixed k.",
author = "Xiao Zhou and Nakano, {Shln Ichi} and Takao Nishizeki",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 1st Annual European Symposium on Algorithms, ESA 1993 ; Conference date: 30-09-1993 Through 02-10-1993",
year = "1993",
doi = "10.1007/3-540-57273-2_76",
language = "English",
isbn = "9783540572732",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "409--418",
editor = "Thomas Lengauer",
booktitle = "Algorithms ESA 1993 – 1st Annual European Symposium, Proceedings",
}