2024-03-29T07:44:40Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000322382023-04-27T10:00:04Z01164:02592:02666:02670
部分k?木の一般化点ランキングGeneralized Vertex - Rankings of Partial k - Treesjpnhttp://id.nii.ac.jp/1001/00032238/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32238&item_no=1&attribute_id=1&file_no=1Copyright (c) 1997 by the Information Processing Society of Japan東北大学大学院情報科学研究科東北大学情報処理教育センター東北大学大学院情報科学研究科カシェムモハメドアブル周暁西関, 隆夫グラフGの全ての点に正整数のラベルを付ける。各ラベルiについて、iより大きなラベルの点を全てGから除去したとき、各連結成分がラベルiの点を高々c個しかもたないならば、このラベル付けをc?点ランク付けという。ここでcは正整数とする。最小の個数のラベルで部分k木をc?点ランク付けする多項式時間アルゴリズムを本文は与える。ここでkは定数とする。1?点ランク付けは単に点ランク付けと呼ばれるが、本文のアルゴリズムは、1?点ランク付けを求める既知のアルゴリズムより高速である。A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with inters such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. We present a polynomial time algorithm to find a c-vertex-ranking of a partial k-tree using the minimum number of ranks for ranks for any positive integer c and any bounded integer k. Our algorithm is faster than the best algorithm known for the ordinary vertex-ranking, that is, 1-vertex-ranking.AN1009593X情報処理学会研究報告アルゴリズム(AL)199726(1996-AL-056)27341997-03-142009-06-30