IEICE TRANSACTIONS on Information
Cost Total Colorings of Trees
Summary :
A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.
- Publication
- IEICE TRANSACTIONS on Information Vol.E87-D No.2 pp.337-342
- Publication Date
- 2004/02/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shuji ISOBE, Xiao ZHOU, Takao NISHIZEKI, "Cost Total Colorings of Trees" in IEICE TRANSACTIONS on Information,
vol. E87-D, no. 2, pp. 337-342, February 2004, doi: .
Abstract: A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.
URL: https://global.ieice.org/en_transactions/information/10.1587/e87-d_2_337/_p
Copy
@ARTICLE{e87-d_2_337,
author={Shuji ISOBE, Xiao ZHOU, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={Cost Total Colorings of Trees},
year={2004},
volume={E87-D},
number={2},
pages={337-342},
abstract={A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Cost Total Colorings of Trees
T2 - IEICE TRANSACTIONS on Information
SP - 337
EP - 342
AU - Shuji ISOBE
AU - Xiao ZHOU
AU - Takao NISHIZEKI
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2004
AB - A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.
ER -
English
