Combinatorial Relaxation Algorithm for the Entire Sequence of the Maximum Degree of Minors

详细信息    查看全文

• 作者：Shun Sato
• 关键词：Combinatorial relaxation ; Degree of minor ; Valuated bimatroid ; Discrete concavity
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：77
• 期：3
• 页码：815-835
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

This paper presents an efficient “combinatorial relaxation” algorithm for computing the entire sequence of the maximum degree of minors in rational function matrices, whereas the previous algorithms find them separately for a specified order k. The efficiency of the algorithm is based on the discrete concavity related to valuated bimatroids.