首页> 外文会议>Special event on analysis of experimental algorithms >The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation
【24h】

The Complexity of Subtree Intersection Representation of Chordal Graphs and Linear Time Chordal Graph Generation

机译:和弦图的子树相交表示和线性时间和弦图生成的复杂性

获取原文

摘要

It is known that any chordal graph on n vertices can be represented as the intersection of n subtrees in a tree on n nodes [5]. This fact is recently used in [2] to generate random chordal graphs on n vertices by generating n subtrees of a tree on n nodes. It follows that the space (and thus time) complexity of such an algorithm is at least the sum of the sizes of the generated subtrees assuming that a tree is given by a set of nodes. In [2], this complexity was mistakenly claimed to be linear in the number m of edges of the generated chordal graph. This error is corrected in [3] where the space complexity is shown to be Ω(mn~(1/4)). The exact complexity of the algorithm is left as an open question. In this paper, we show that the sum of the sizes of n subtrees in a tree on n nodes is Θ(m(n~(1/2))). We also show that we can confine ourselves to contraction-minimal subtree intersection representations since they are sufficient to generate every chordal graph. Furthermore, the sum of the sizes of the subtrees in such a representation is at most 2m + n. We use this result to derive the first linear time random chordal graph generator. In addition to these theoretical results, we conduct experiments to study the quality of the chordal graphs generated by our algorithm and compare them to those in the literature. Our experimental study indicates that the generated graphs do not have a restricted structure and the sizes of maximal cliques are distributed fairly over the range. Furthermore, our algorithm is simple to implement and produces graphs with 10000 vertices and 4.10~7 edges in less than one second on a laptop computer.
机译:众所周知,在n个顶点上的任何弦图都可以表示为n个节点上树中n个子树的交集[5]。最近在[2]中使用此事实,通过在n个节点上生成树的n个子树,在n个顶点上生成随机弦弦图。随之而来的是,这种算法的空间(以及时间)复杂度至少是所生成子树大小的总和,前提是假设树是由一组节点给定的。在[2]中,这种复杂性被错误地认为在生成的弦图的边数m中是线性的。在[3]中纠正了这个错误,其中空间复杂度显示为Ω(mn〜(1/4))。该算法的确切复杂性尚待解决。在本文中,我们证明了在n个节点上的树中n个子树的大小之和为Θ(m(n〜(1/2)))。我们还表明,我们可以将自己限于收缩-最小子树相交表示,因为它们足以生成每个弦图。此外,在这种表示中,子树的大小之和最多为2m + n。我们用这个结果来推导第一个线性时间随机弦图发生器。除了这些理论结果之外,我们还进行实验以研究由我们的算法生成的弦图的质量,并将其与文献中的弦图进行比较。我们的实验研究表明,生成的图不具有受限的结构,最大派系的大小在整个范围内公平分布。此外,我们的算法易于实现,并且在便携式计算机上用不到一秒钟的时间即可生成具有10000个顶点和4.10〜7个边的图形。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号