2024-03-28T23:57:29Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000904182023-04-27T10:00:04Z01164:02592:07086:07087
木の最小コスト点彩色の列挙と一意性についてEnumeration and Uniqueness for Optimal Cost Vertex Colorings of Treesjpnhttp://id.nii.ac.jp/1001/00090401/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=90418&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan東海大学大学院理学研究科数理科学専攻東海大学理学部情報数理学科木坂, 健人松井, 泰子本稿では,木に対する最小コスト点彩色が一意でない場合,それらを重複無く全て列挙するアルゴリズムを提案する.一般グラフの最小コスト点彩色問題はNP困難であるが,1997年,Kroon et. al.は木に対する線形時間アルゴリズムを提案した.しかし,最小コスト点彩色が一意で無い場合,それらを列挙するアルゴリズムはまだ提案されていない.そこで我々は初めて列挙アルゴリズムを提案する.本稿では,与えられた木Tに対し,最小コスト点彩色を1つ当たりO(nd2)時間で列挙するアルゴリズムを提案する.ただし,nはTの頂点数,dはTの最大次数である.また,木の最小コスト点彩色に対して任意の十分大きな色数が与えられた時,その色を全て使用する木の特徴付けを行う.In this paper, we propose an algorithm for enumerating all the optimal cost vertex colorings of given trees without repetitions if the optimal cost vertex coloring is not unique. The optimal cost vertex coloring problem is NP-hard for arbitrary graphs. In 1997, Kroon et. al. showed the problem can be solved in a linear time for trees. However, there is no algorithm for enumerating all optimal cost vertex colorings of trees. We first give an enumeration algorithm for the problem. For a given tree, our algorithm can enumerate all optimal vertex colorings in O(nd2) time for each where n is the number of vertices of T, d is the number of maximum degree of T. Moreover, we characterize trees which use an arbitrary number of colors for optimal cost vertex coloring.AN1009593X研究報告アルゴリズム(AL)2013-AL-14314162013-02-222013-02-15