【摘 要】
：
本文在匈牙利算法和HK算法的基础上,提出了一种二部图无权最大匹配的符号OBDD算法.实验结果表明:在处理大密度或大规模图时,符号算法具有明显优势.2预备知识3二部图的符号OBD
【机 构】
：
桂林电子工业学院计算机系,桂林,541004
【出 处】
：
2005年全国理论计算机科学学术年会
论文部分内容阅读
本文在匈牙利算法和HK算法的基础上,提出了一种二部图无权最大匹配的符号OBDD算法.实验结果表明:在处理大密度或大规模图时,符号算法具有明显优势.2预备知识3二部图的符号OBDD表示4二部图无权最大匹配的符号OBDD算法实验结果表明,随着二部图密度的增长,其他算法的执行时间不断地增长或内存溢出,而符号OB-DD算法执行时间则逐渐减少,这主要是由于大量共享结点的存在,二部图对应的OBDD反而越来越小,体现了其结构高紧凑性的优点.所以,在相同的条件下,符号OBDD算法所需的存储空间较少,从而有效地抑制了状态爆炸的发生.以上数据表明:本文所提的符号算法具有较低的空间复杂度,在处理高密度或大规模图时具有明显优势.
其他文献
“只要我们在一起,哪都是家”.这是科幻灾难电影《后天》里面的一句经典台词,这句话也适用于失去家园的灾区人民.今年7月的第九号台风“威马逊”已经在我国三次登陆,横扫海南
本文提出了一种求解带度约束的最小代价组播路由树算法DCMST(Degree-ConstrainedMinimumSteinerTree),运用迭代思想,每次迭代执行两个过程:构建初始可行解和邻域搜索,寻找满
摄影师提了个绝妙建议:“咱去景山上拍张照片吧.”rn不出我所料,徐定茂同意了.采访了他两三个小时,我知道他是个好说话的人.rn他供职的单位在沙滩后街,去景山一箭之遥.摄影师
途牛的愿景是成为旅游的入口.上市之后,我们离目标更近了.rn2006年途牛创立之初,就专注于在线休闲旅游的细分市场.当时在线休闲旅游市场几乎是零,线下休闲旅游服务存在着很大
本文介绍了成本分析理论,并结合自动入侵响应的方法特点,将成本分析理论应用于AAIRS中,构架了一个基于成本分析的自适应入侵响应系统CAIRS,研究了该模型中的分析模块和成本分
当BAT三家对车联网虎视眈眈的时候,叶志华嗅到了一丝危险的气息.rn叶志华是钛马信息网络技术有限公司总裁.在BAT车联网大战吹响号角时,钛马早已卷入其中.今年4月份百度推出的
谁还关心“92派’？至少他们自己在关心自己，也期待更多人体会到在他们身上曾经发生的思想解放的惊人力量。
5月中旬,杜宏路作为一家美国科技公司的代表来到重庆,与重庆市科技创投引导基金谈判,希望通过发展更智能的交通信息化系统,解决重庆江北区与南岸区的交通拥堵、停车难问题.rn
本文证明了在Metric情况下内点带权的最小生成树问题是NPhard的.给出了一个近似度为3．582的近似算法,并对算法的正确性和近似度进行了详细的分析和证明.本文是关于内点带权的
本文给出了具有结点失效的3-状态设备网络2-终端可靠性模型,并给出了这种模型可靠度的基本计算思想.结合已有的归约公式,我们还给出了两类特殊的具有结点失效网络可靠度的算