• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Foundations of Computer Science(FCS'05); 20050627-30; Las Vegas,NV(US) >On-Line Ranking Algorithms for Trees
【24h】

On-Line Ranking Algorithms for Trees

机译：树的在线排名算法

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

摘要

A node k-ranking of a graph G = (V, E) is a proper node coloring C: V → {1, 2, ..., k} such that any path in G with end nodes x, y fulfilling C(x) = C(y) contains an internal node z with C(z) > C(x). In the on-line version of this problem, the nodes v_1, v_2, ... , v_n are coming one by one in an arbitrary order; and only the edges of the induced subgraph G[{v_1, v_2, ... , v_i}] are known when the color of v_i has to be chosen. This paper gives an on-line ranking algorithm for general trees and an optimal on-line ranking algorithm for the special trees, K_(1,n), also called stars.
机译：图G =（V，E）的节点k排序是将C着色为适当的节点：V→{1,2，...，k}，使得G中端节点x，y的任何路径都满足C（ x）= C（y）包含一个内部节点z，其中C（z）> C（x）。在此问题的在线版本中，节点v_1，v_2，...，v_n以任意顺序一个接一个地移动；当必须选择v_i的颜色时，只有诱导子图G [{v_1，v_2，...，v_i}]的边缘是已知的。本文给出了一般树的在线排序算法和特殊树的最优在线排序算法，K_（1，n），也称为星。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号