兰州大学机构库 >数学与统计学院
图的路匹配
Alternative TitlePath-matchings of graphs
晏静之
Thesis Advisor张和平
2008-05-20
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
Keyword路匹配 完美路匹配 Gallai-Edmonds 型结构分解 因子临界图 D1导出图 正则图 无 K1,t图 联接数 极集合 路匹配数
Abstract作为匹配和拟阵交的共同推广, Cunningham 和 Geelen 在 1996 年引入了图的路匹配的概念. 他们指出许多领域的问题都可以转化为路匹配问题, 也就是说,利用路匹配可以解决例如匹配、拟阵、多面体以及代数等很多方面的问题. 作为路匹配的应用, 他们给出了可匹配集合多面体的强多项式分离算法, 并证明了最大路匹配的值就等于给定图所确定的匹配拟阵中顶点集合的秩, 同时也等于 Tutte 矩阵的秩等等.
Other AbstractAs a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. They showed that problems in many fields can be transformed into path-matching problems. In other words, by using path-matchings many problems in matchings, matroid, polyhedron and algebra can be solved. As the applications of path-matchings, they developed a strongly polynomial separation algorithm for the matchable set polyhedron, and proved that the maximum value of a path-matching is the rank of vertices set in the matching matroid determined by some given graph, and is also equal to the rank of an Tutte matrix, etc.
URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/224630
Collection数学与统计学院
Recommended Citation
GB/T 7714
晏静之. 图的路匹配[D]. 兰州. 兰州大学,2008.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[晏静之]'s Articles
Baidu academic
Similar articles in Baidu academic
[晏静之]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[晏静之]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.