检索结果-内蒙古大学图书馆

高等学校计算数学学报 2006年第4期28卷 318-328页

作者：焦波邱涤珊马满好凌云国防科技大学信息系统与管理学院指挥自动化系4室国防科技大学信息系统与管理学院指挥自动化系4室长沙 410073

1引言b匹配问题是匹配问题的推广,它在国内研究较少,但在国外已有一定研究．文献[3]给出了b匹配的应用实例,文献[4]～[6]给出了b匹配算法的研究成果,这些算法主要有两类:第一类为通过b匹配问题的线性规划模型求解,第二类为将b匹配问题... 详细信息

1引言b匹配问题是匹配问题的推广,它在国内研究较少,但在国外已有一定研究．文献[3]给出了b匹配的应用实例,文献[4]～[6]给出了b匹配算法的研究成果,这些算法主要有两类:第一类为通过b匹配问题的线性规划模型求解,第二类为将b匹配问题转化为匹配问题求解．本文首次提出增广迹的概念,证明定理1[M为G的最大b匹配(?)G中不存在M增广迹]的正确性,并仿照最大匹配的花算法设计最大b匹配的花算法,即直接对b匹配问题求解,避免将b匹配问题转化为匹配问题,这样就可以将各顶点b(vi)

关键词： b matching alternating network Hungarian network blossom algorithm complexity.

来源：评论

学校读者我要写书评

暂无评论

An optimized strategy for inter-satellite links assignments in GNSS

引用

ADVANCES IN SPACE RESEARCH 2023年第1期71卷 720-730页

作者： Xu, Bingbing Han, Kai Ren, Qianyi Gong, Wenbin Shao, Fengwei Wang, Yukai Chang, Jiachao Chinese Acad Sci Innovat Acad Microsatellites Shanghai 201210 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China

Inter-Satellite Links (ISLs) can effectively enhance the Global Navigation Satellite System (GNSS) performance, such as communi-cation and ranging performance. These performances would have been improved by disposing sparsely of ground stations and ISLs. Here, we demonstrate a topology scheduling strategy based on Signed Variance and blossom algorithm (SV-blossom) to promote the topology performance of GNSS. We also analyze the effect of this strategy on the robustness of the ranging information quality of the ISLs assignments system. For the domestic and overseas satellite communication Time Delay (TD) and Position Dilution of Pre-cision (PDOP), by analyzing the relation of satellites, a set of the ISLs cost models is established, and the cost matrix is obtained. The final ISLs assignments result is obtained by processing the link cost matrix with the blossom algorithm in the graph theory. In order to verify the rationality of the SV-blossom strategy, a typical BDS-3 simulation scene with 10080 min is built to test these performances of ISLs. The final results show that the ranging information quality of the SV-blossom strategy is greatly improved compared with recently published strategies, and the proposed links assignments mechanism has good robustness.(c) 2022 COSPAR. Published by Elsevier B.V. All rights reserved.

关键词： Inter-satellite links Links assignments GNSS Signed variance blossom algorithm

来源：评论

学校读者我要写书评

暂无评论

Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs

引用

COMPUTERS & OPERATIONS RESEARCH 2017年第Nov.期87卷 107-113页

作者： Wohlk, Sanne Laporte, Gilbert Aarhus Univ CORAL Dept Econ & Business Econ Fuglesangs Alle 4 DK-8210 Aarhus V Denmark HEC Montreal GERAD 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada HEC Montreal Canada Res Chair Distribut Management 3000 Chemin Cote St Catherine Montreal PQ H3T 2A7 Canada

The aim of this paper is to computationally compare several algorithms for the Minimum Cost Perfect Matching Problem on an undirected complete graph. Our work is motivated by the need to solve large instances of the Capacitated Arc Routing Problem (CARP) arising in the optimization of garbage collection in Denmark. Common heuristics for the CARP involve the optimal matching of the odd-degree nodes of a graph. The algorithms used in the comparison include the CPLEX solution of an exact formulation, the LEDA matching algorithm, a recent implementation of the blossom algorithm, as well as six constructive heuristics. Our results show that two of the constructive heuristics consistently exhibit the best behavior compared with the other four. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Perfect matching problem blossom algorithm Capacitated arc routing problem Rural postman problem Garbage collection

来源：评论

学校读者我要写书评

暂无评论

Robust Virtual Unrolling of Historical Parchment XMT Images

引用

IEEE TRANSACTIONS ON IMAGE PROCESSING 2018年第4期27卷 1914-1926页

作者： Liu, Chang Rosin, Paul L. Lai, Yu-Kun Hu, Weiduo Beihang Univ Sch Astronaut Beijing 100191 Peoples R China Cardiff Univ Sch Comp Sci & Informat Cardiff CF24 3AA S Glam Wales

We develop a framework to virtually unroll fragile historical parchment scrolls, which cannot be physically unfolded via a sequence of X-ray tomographic slices, thus providing easy access to those parchments whose contents have remained hidden for centuries. The first step is to produce a topologically correct segmentation, which is challenging as the parchment layers vary significantly in thickness, contain substantial interior textures and can often stick together in places. For this purpose, our method starts with linking the broken layers in a slice using the topological structure propagated from its previous processed slice. To ensure topological correctness, we identify fused regions by detecting junction sections, and then match them using global optimization efficiently solved by the blossom algorithm, taking into account the shape energy of curves separating fused layers. The fused layers are then separated using as-parallel-as-possible curves connecting junction section pairs. To flatten the segmented parchment, pixels in different frames need to be put into alignment. This is achieved via a dynamic programming-based global optimization, which minimizes the total matching distances and penalizes stretches. Eventually, the text of the parchment is revealed by ink projection. We demonstrate the effectiveness of our approach using challenging real-world data sets, including the water damaged fifteenth century Bressingham scroll.

关键词： X-ray parchment as parallel as possible flatten blossom algorithm dynamic programming ink projection

来源：评论

学校读者我要写书评

暂无评论

FINDING MAXIMUM EDGE-DISJOINT PATHS BETWEEN MULTIPLE TERMINALS

引用

SIAM JOURNAL ON COMPUTING 2023年第5期52卷 1230-1268页

作者： Iwata, Satoru Yokoi, Yu Univ Tokyo Dept Math Informat Tokyo 1138656 Japan Hokkaido Univ Inst Chem React Design & Discovery Sapporo 0010021 Japan Tokyo Inst Technol Sch Comp Dept Math & Comp Sci Tokyo 1528550 Japan

Let G = (V, E) be a multigraph with a set T \subseteq V of terminals. A path in G is called a T-path if its ends are distinct vertices in T and no internal vertices belong to T. In 1978, Mader showed a characterization of the maximum number of edge-disjoint T-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint T-paths. The algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint T-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds [Canad. J. Math., 17, 1965, pp. 449--467]. When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint T-paths. From this certificate, one can obtain the Edmonds-Gallai type decomposition introduced by SeboH \ and SzegoH \ [Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization, LNCS 3064, Springer, Berlin, 2004, pp. 256--270]. The algorithm runs in O(1E12) time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of T-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.

关键词： combinatorial optimization blossom algorithm multicommodity flow

来源：评论

学校读者我要写书评

暂无评论

Clustering analysis of microRNA and mRNA expression data from TCGA using maximum edge-weighted matching algorithms

引用

BMC MEDICAL GENOMICS 2019年第1期12卷 1-27页

作者： Ding, Lizhong Feng, Zheyun Bai, Yongsheng Indiana State Univ Dept Biol Terre Haute IN 47809 USA Indiana State Univ Dept Math & Comp Sci Terre Haute IN 47809 USA Univ Michigan Dept Internal Med Ann Arbor MI 48105 USA

Background microRNA (miRNA) is a short RNA (similar to 22 nt) that regulates gene expression at the posttranscriptional level. Aberration of miRNA expressions could affect their targeting mRNAs involved in cancer-related signaling pathways. We conduct clustering analysis of miRNA and mRNA using expression data from the Cancer Genome Atlas (TCGA). We combine the Hungarian algorithm and blossom algorithm in graph theory. Data analysis is done using programming language R and Python. Methods We first quantify edge-weights of the miRNA-mRNA pairs by combining their expression correlation coefficient in tumor (T_CC) and correlation coefficient in normal (N_CC). We thereby introduce a bipartite graph partition procedure to identify cluster candidates. Specifically, we propose six weight formulas to quantify the change of miRNA-mRNA expression T_CC relative to N_CC, and apply the traditional hierarchical clustering to subjectively evaluate the different weight formulas of miRNA-mRNA pairs. Among these six different weight formulas, we choose the optimal one, which we define as the integrated mean value weights, to represent the connections between miRNA and mRNAs. Then the Hungarian algorithm and the blossom algorithm are employed on the miRNA-mRNA bipartite graph to passively determine the clusters. The combination of Hungarian and the blossom algorithms is dubbed maximum weighted merger method (MWMM). Results MWMM identifies clusters of different sizes that meet the mathematical criterion that internal connections inside a cluster are relatively denser than external connections outside the cluster and biological criterion that the intra-cluster Gene Ontology (GO) term similarities are larger than the inter-cluster GO term similarities. MWMM is developed using breast invasive carcinoma (BRCA) as training data set, but can also applies to other cancer type data sets. MWMM shows advantage in GO term similarity in most cancer types, when compared to other algorithms. Conclus

关键词： Cancer miRNAs and mRNAs Gene regulation BRCA TCGA Bipartite graph Graph partitioning Hungarian algorithm blossom algorithm Clustering

来源：评论

学校读者我要写书评

暂无评论

LAYERED-GIVENS TRANSFORMS: TUNABLE COMPLEXITY, HIGH-PERFORMANCE APPROXIMATION OF OPTIMAL NON-SEPARABLE TRANSFORMS 24

LAYERED-GIVENS TRANSFORMS: TUNABLE COMPLEXITY, HIGH-PERFORMA...

引用

24th IEEE International Conference on Image Processing (ICIP)

作者： Li, Bohan Guleryuz, Onur G. Ehmann, Jana Vosoughi, Arash UC Santa Barbara Santa Barbara CA 93106 USA LG Elect San Jose CA USA Google Inc Mountain View CA USA Sony Elect San Jose CA USA

ISBN: (纸本)9781509021758

We introduce layered-Givens transforms (LGTs) which are arbitrary dimensional, tunable-complexity, orthonormal transforms of data. LGTs are formed by layers of data permutations and Givens rotations with the number of layers controlling the overall transform's computational complexity. We propose a novel method for the design of layered-Givens transforms that approximate desired complex transforms (such as MA's, SOTs, etc.) so that most of the performance of the approximated transform is retained at significantly reduced complexity. Key to the LGT performance is the choice of the permutations that arrange the data prior to the Givens rotations. Despite the very highly combinatorial nature of the LGT design problem, we provide an algorithm that finds the optimal parameters (permutation and Givens rotations) for each layer. Our results show that designed LGTs closely approximate desired non-separable transforms at significantly reduced complexity.

关键词： layered-Givens transforms row-column transforms video compression blossom algorithm Hungarian method

来源：评论

学校读者我要写书评

暂无评论

Dynamic matching algorithms in practice 28

Dynamic matching algorithms in practice

引用

28th Annual European Symposium on algorithms, ESA 2020

作者： Henzinger, Monika Khan, Shahbaz Paul, Richard Schulz, Christian University of Vienna Faculty of Computer Science Austria Department of Computer Science University of Helsinki Finland

ISBN: (纸本)9783959771627

In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances. © Monika Henzinger, Shahbaz Khan, Richard Paul, and Christian Schulz.

关键词： blossom algorithm Dynamic Matching Matching

来源：评论

学校读者我要写书评

暂无评论

Even Delta-Matroids and the Complexity of Planar Boolean CSPs

引用

ACM TRANSACTIONS ON algorithmS 2019年第2期15卷 22-22页

作者： Kazda, Alexandr Kolmogorov, Vladimir Rolinek, Michal IST Austrin Campus 1 Klosterneuburg 3400 Austria Charles Univ Prague Dept Algebra Sokolovska 83 Prague 18675 8 Czech Republic Max Planck Inst Intelligent Syst Max Planck Ring 4 D-72076 Tubingen Germany

The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Delta-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Delta-matroids, we then extend the tractability result to larger classes of Delta-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat: We represent Delta-matroids by lists of tuples, while the last two use a representation by matrices. Since an n x n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Delta-matroids.

关键词： Constraint satisfaction problem delta-matroid blossom algorithm

来源：评论

学校读者我要写书评

暂无评论

Take the Right Seat: The Influence of Occupancy Schemes on Performance Indicators of Lighting in Open Plan Offices

引用

ENERGIES 2022年第9期15卷 3378-3378页

作者： Hammes, Sascha Weninger, Johannes Pfluger, Rainer Pohl, Wilfried Univ Innsbruck Unit Energy Efficient Bldg A-6020 Innsbruck Austria Bartenbach GmbH A-6071 Aldrans Austria

Work processes and sociological structures can differ significantly between organizations. These organizational aspects determine user behavior, which in turn exerts considerable influence on the key performance indicators of artificial lighting systems. Accordingly, the use of generalized assumptions about user behavior in the building design phase can lead to large discrepancies between design and operation. In the following work, the possible influences of different occupancy schemes, an essential aspect of user behavior and shaped by the organization, on energy demand and workplace-related daylight dose are evaluated. For this purpose, calculations are made based on real measurement data of an open-plan office with zoned lighting. Multi-level calculation models are used to determine improved user distributions in the room to ensure optimization according to the desired target criteria. The results show that occupancy schemes have a significant impact on energy demand, contributing significantly to overall building performance, but only slightly to workplace-related light exposure rates in terms of total daily light dose. A correlated influence on the target criteria could not be demonstrated, but given the minor influence on daily light dose, the optimization of planning and operation can be focused on energy efficiency.

关键词： energy efficiency daily light dose artificial lighting occupancy schemes blossom algorithm Hungarian algorithm assignment problems

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：