論文

査読有り
2013年7月

A Linear Time Algorithm for L(2,1)-Labeling of Trees

ALGORITHMICA
  • Toru Hasunuma
  • ,
  • Toshimasa Ishii
  • ,
  • Hirotaka Ono
  • ,
  • Yushi Uno

66
3
開始ページ
654
終了ページ
681
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1007/s00453-012-9657-z
出版者・発行元
SPRINGER

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|a parts per thousand yen2 if x and y are adjacent and |f(x)-f(y)|a parts per thousand yen1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)->{0,aEuro broken vertical bar,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Delta (4.5) n) for more than a decade, and an O(min{n (1.75),Delta (1.5) n})-time algorithm has appeared recently, where Delta and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.

Web of Science ® 被引用回数 : 6

リンク情報
DOI
https://doi.org/10.1007/s00453-012-9657-z
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000317973900008&DestApp=WOS_CPL
URL
http://dblp.uni-trier.de/db/journals/algorithmica/algorithmica66.html#journals/algorithmica/HasunumaIOU13

エクスポート
BibTeX RIS