首页> 外文会议>Workshop on Combinatorial and Algorithmic Aspects of Networking >Combinatorial Algorithms for Listing Paths in Minimal Change Order
【24h】

Combinatorial Algorithms for Listing Paths in Minimal Change Order

机译:最小变化顺序中列出路径的组合算法

获取原文
获取外文期刊封面目录资料

摘要

Combinatorial algorithms that list combinatorial objects in minimal change order are of fundamental interest in computer science and mathematics. In minimal change ordering, successive elements differ in some pre-specified small way. In this paper, we deal with the generation of paths in a special type of minimal change ordering, the revolving door ordering. We propose a simple algorithm to list all paths in a complete graph, K_n, with n vertices in revolving door order such that each path is generated exactly once. The algorithm is built using space and time efficient schemes that list all spanning paths and "path sets" in revolving door order. Our algorithm is optimal in the sense that it operates in constant amortized time (CAT) and uses linear space.
机译:在最小的变化顺序中列出组合对象的组合算法对计算机科学和数学是基本兴趣。在最小的变化排序中,连续的元素在一些预先指定的小路中不同。在本文中,我们处理了一种特殊类型的最小变化排序,旋转门口的道路。我们提出了一种简单的算法来列出完整图中的所有路径,K_N,在旋转门单中的N个顶点,使得每条路径都是完全生成一次。该算法使用空间和时间高效方案构建,该方案列出所有跨越路径和旋转门单中的“路径集”。我们的算法在恒定的摊销时间(CAT)中运行并使用线性空间,这是最佳的。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号