TESTING κ-EDGE-CONNECTIVITY OF DIGRAPHS

来源 :系统科学与复杂性学报(英文版) | 被引量 : 0次 | 上传用户:liongliong452
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
This paper presents an algorithm that tests whether a given degree-bounded digraph is κ-edge-connected or ε-far from κ-edge-connectivity. This is the first testing algorithm for κ-edge-connectivity of digraphs whose running time is independent of the number of vertices and edges. A digraph of n vertices with degree bound d is ε-far from κ-edge-connectivity if at least εdn edges have to be added or deleted to make the digraph κ-edge-connected, preserving the degree bound. Given a constant error parameter ε and a degree bound d, our algorithm always accepts all κ-edge-connected digraphs and rejects all digraphs that is ε-far from κ-edge-connectivity with probability at least 2/3. It runs in O(d (c/εd)~κlog 1/εd O)(c > 1 is a constant) time when input digraphs are restricted to be (κ- 1)-edge connected and runs in O(d (cκ/εd)~κ log κ/εdO)(c > 1 is a constant) time for general digraphs.
其他文献
This paper considers identification of the nonlinear autoregression with exogenous inputs (NARX system). The growth rate of the nonlinear function is required b
日常生活中,我们都喜欢吃一些腌制品,特别是秋冬季节,家家户户都会腌咸鱼过年.然而这些腌制食物的亚硝基化合物含量较高,有致癌的危险.
This paper presents the notions of exact observability and exact detectability for Markov jump linear stochastic systems of Ito type with multiplicative noise (
This paper analyzes performance of optimal channel estimation and multiuser detection (MUD) in a block-fading code-division multiple-access (CDMA) channel on th
In the application of multiple-processor systems some processors or links in a system may not function properly, thus the fault diagnosis is one of the most imp
In communication networks (CNs), the uncertainty is caused by the dynamic nature of the traffic demands. Therefore there is a need to incorporate the uncertaint
人常说“老有所为”“老有所乐”,而眼下一些老人们的“所为”却多是任性而为、胡乱而为,并由此成就了他们的“所乐”.比如街头“暴走团”引起交通混乱乃至车祸,比如当街讹诈
期刊
This work is conced with consensus control for a class of leader-following multi-agent systems (MASs). The information that each agent received is corrupted by
试验设计了复火温度(80、100、120℃)和复火时间(1、2、3h)二因素三水平试验对杜仲绿茶精制加工过程中品质成分变化的影响。结果表明:叶绿素、脱镁叶绿素、蛋白质、氨基酸、
This paper discusses the ergodicity of a linear stochastic partial differential equation driven by Lévy noise.