On Module-Composed Graphs

机译：在模块组成的图上

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

In this paper we introduce module-composed graphs, i.e. graphs which can be defined by a sequence of one-vertex insertions υ1,... ,υn, such that the neighbourhood of vertex υi, 2 ≤ i ≤ n, forms a module of the graph defined by vertices υ1,..., υi-1. We show that module-composed graphs are HHDS-free and thus homogeneously orderable, weakly chordal, and perfect. Every bipartite distance hereditary graph and every trivially perfect graph is module-composed. We give an (O)(|V| ? (|V| + |E|)) time algorithm to decide whether a given graph G = (V, E) is module-composed and construct a corresponding module-sequence. For the case of bipartite graphs, we show that the set of module-composed graphs is equivalent to the well known class of distance hereditary graphs, which implies linear time algorithms for their recognition and construction of a corresponding module-sequence using BFS and Lex-BFS.

机译：在本文中，我们介绍由模块组成的图，即可以由一系列单顶点插入υ1，...，υn定义的图，使得顶点υi，2≤i≤n的邻域形成由顶点υ1，...，υi-1定义的图。我们显示模块组成的图是无HHDS的，因此可均匀排序，弱和弦且完美。每个二分距离遗传图和每个平凡完美的图都是由模块组成的。我们给出（O）（| V |？（| V | + | E |））时间算法，以确定给定图G =（V，E）是否由模块组成，并构造相应的模块序列。对于二部图，我们证明了模块组成图的集合等同于众所周知的距离遗传图类，这暗示了线性时间算法可以识别它们并使用BFS和Lex-构造相应的模块序列。 BFS。

著录项

来源
《Graph-theoretic concepts in computer science》|2009年|p.166-177|共12页
会议地点 Montpellier(FR);Montpellier(FR)
作者
Frank Gurski; Egon Wanke;
展开▼
作者单位

Heinrich-Heine-University DuesseldorfInstitute of Computer Science D-40225 Duesseldorf, Germany;

Heinrich-Heine-University DuesseldorfInstitute of Computer Science D-40225 Duesseldorf, Germany;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算机网络;
关键词
special graph classes; homogeneous sets; HHDS-free graphs; distance hereditary graphs; bipartite graphs;

机译：特殊图类；齐次集无HHDS图；距离遗传图；二部图;

相似文献

外文文献
中文文献
专利

1. GRAPH EQUATIONS FOR LINE GRAPHS, JUMP GRAPHS, MIDDLE GRAPHS, LITACT GRAPHS AND LICT GRAPHS [J] . B. BASAVANAGOUD, VEENA N. MATHAD Acta Ciencia Indica. Mathematics . 2005,第3期

机译：线性图，跳跃图，中图，Litact图和LICT图的图形方程
2. RSA and Public-Key Cryptography Introduction to Cryptography Cryptography: Theory and Practice Algebraic Aspects of Cryptography Elliptic Curves: Number Theory and Cryptography Elliptic Curves in Cryptography Modern Cryptography, Probabilistic Proofs, and Pseudorandomness Foundations of Cryptography: Basic Tools The Design of Rijndael: AES --- the Advanced Encryption Standard Handbook of Applied Cryptography [J] . Susan Landau Bulletin of the American Mathematical Society . 2004,第3期

机译：RSA和公钥密码学密码学简介密码学：密码学的理论和实践椭圆曲线的密码学：密码学中的数论和密码学椭圆曲线现代密码学，概率证明和伪随机性基础密码学：基本工具Rijndael的设计： -应用密码学高级加密标准手册
3. Maximal outerplanar graphs as chordal graphs, path-neighborhood graphs, and triangle graphs [J] . R.C. LASKAR, HENRY MARTYN MULDER, B. NOVICK The Australasian journal of combinatorics . 2012,第Null期

机译：最大外平面图，如弦图，路径邻域图和三角形图
4. On Module-Composed Graphs [C] . Prank Gurski, Egon Wanke International Workshop on Graph-Theoretic Concepts in Computer Science . 2010

机译：在模块组成的图表上
5. Genome Assembly of Long Error-Prone Reads Using de Bruijn Graphs and Repeat Graphs [D] . Yuan, Jeffrey. 2019

机译：使用de bruijn图表和重复图来读取长时间错误的基因组组合
6. Venereal Disease Bibliography 1966-1970 Venereal Disease Bibliography For 1971 Abortion Bibliography For 1970 Abortion Bibliography For 1971 Drugs of Addiction and Non-Addiction Their Use and Abuse. A Comprehensive Bibliography 1960-1969 Drug Abuse Bibliography For 1970 Drug Abuse Bibliography For 1971 [O] . Rosanne Labree 1973

机译：性病参考书目1966-1970年1971年性病参考书目1970年流产参考书目1971年流产参考书目成瘾和非成瘾药物其使用和滥用。 1960-1969年的综合书目1970年的药物滥用书目1971年的药物滥用书目
7. A note on module-composed graphs [O] . Gurski, Frank 2007

机译：关于模块组成图的说明

On Module-Composed Graphs

摘要

著录项

相似文献

相关主题

期刊订阅