...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Labeling bipartite permutation graphs with a condition at distance two
【24h】

Labeling bipartite permutation graphs with a condition at distance two

机译：用距离为2的条件标记二分置换图

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An L(p, q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0, 1,...,lambda} such that vertical bar f (u) - f(v)vertical bar >= p if u and v are adjacent, and vertical bar f(u) - f(v)vertical bar >= q if u and v are at distance 2 apart. The minimum value of lambda for which G has L(p, q)-labeling is denoted by lambda(p,q)(G). The L(p, q)-labeling problem is related to the channel assignment problem for wireless networks. In this paper, we present a polynomial time algorithm for computing L(p, q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p-1)+q(bc(G)-2), where bc(G) is the biclique number of G. Since lambda(p,q)(G) >= p + q(bc(G) - 2) for any bipartite graph G, the upper bound is at most p - 1 far from optimal.
机译：图G的L（p，q）标注是从G的顶点到一组非负整数{0，1，...，lambda}的赋值f，以使竖线f（u）-f （v）如果u和v相邻，则竖线> = p，如果u和v相距2，则竖线f（u）-f（v）竖线> = q。 G具有L（p，q）标记的lambda的最小值由lambda（p，q）（G）表示。 L（p，q）标记问题与无线网络的信道分配问题有关。在本文中，我们提出了一种多项式时间算法，用于计算二分置换图G的L（p，q）-标记，使得最大标记最多为（2p-1）+ q（bc（G）-2），其中bc（G）是G的双斜数。由于任何二分图G的lambda（p，q）（G）> = p + q（bc（G）-2），所以上限最多为p-1远非最佳。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号