2024-03-28T20:11:49Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000316492023-04-27T10:00:04Z01164:02592:02600:02602
L(2,1)-labeling of bipartite permutation graphsBipartite permutation graphのL(2 1)ラベリングenghttp://id.nii.ac.jp/1001/00031649/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31649&item_no=1&attribute_id=1&file_no=1Copyright (c) 2007 by the Information Processing Society of Japan岩手大学工学部情報システム工学科荒木, 徹グラフ G の L(2 1)ラベリングとは,G の頂点集合から非負整数の集合{0 1 … λ}への写像fであり,u vが隣接していれば|f(u)-f(v)| ? 2,u v間の距離が2なら|f(u)-f(v)| ?1となるものである.グラフGが L(2 1)ラベリングを持つ最小のλの値をλ(G)と表す.この問題は,無線ネットワークのチャネル割り当て問題をモデル化したものである.本論文では,bipartite permutation graphに対して L(2 1)ラベリングを求める多項式時間アルゴリズムを示す.提案アルゴリズムのラベリングで用いられる最大のラベルは高々λ(G)+1であり,最適に近いラベリングを計算する.An L(2, l)-labeling of a graph G is an assignment / from vertices of G to the set of non-negative integers {0,1,..., λ} such that |f(u) -f(v)| 竕・ 2 if u and v are adjacent, and |f(u) -f(v)|竕・1 if u and v are at distance 2 apart. The minimum value of λ for which G has L(2, l)-labeling is denoted by λ(G). The L(2, l)-labeling problem is related to the channel assignment problem for wireless networks. In this paper, we present a polynomial time algorithm for computing L{2, l)-labeling of a bipartite permutation graph G such that the largest label is at most λ{G) + 1, which is a nearly optimal value.AN1009593X情報処理学会研究報告アルゴリズム(AL)200792(2007-AL-114)9162007-09-212009-06-30