Register
 ALL Title Author Keyword Sponsors Type Publication date Submitted Time Subject Conference Name Source Categories KOS Subject Advisor ORCID Advanced
 ISCAS OpenIR  > 软件所图书馆  > 期刊论文
 Title: Computing the Degree of Determinants via Combinatorial Relaxation Author: Kazuo Murota Source: SIAM Journal on Computing Issued Date: 1995 Volume: 24, Issue:4, Pages:765 - 796 Indexed Type: 其他 Cooperation Status: 其它 English Abstract: Let $A(x)=(A_{ij}(x))$ be a square matrix with $A_{ij}$ being a polynomial in $x$. This paper proposes "combinatorial relaxation" type algorithms for computing the degree of the determinant, $\delta(A) = \deg_x \det A(x)$, based on its combinatorial upper bound $\widehat \delta(A)$, which is defined in terms of the maximum weight of a perfect matching in an associated graph. The graph is bipartite for a general square matrix $A$ and nonbipartite for a skew-symmetric $A$. The algorithm transforms $A$ to another matrix $A'$ for which $\delta(A) = \delta(A') = \widehat \delta(A')$ with successive elementary operations. The algorithm is efficient, making full use of the fast algorithms for weighted matchings; it is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. Language: 英语 Content Type: 期刊论文 URI: http://ir.iscas.ac.cn/handle/311060/1330 Appears in Collections: 软件所图书馆_期刊论文

 Files in This Item:
File Name/ File Size Content Type Version Access License
bj01135893.pdf（1804KB）----限制开放 联系获取全文

 Recommended Citation: Kazuo Murota. Computing the Degree of Determinants via Combinatorial Relaxation[J]. SIAM Journal on Computing,1995-01-01,24(4):765 - 796.
 Service Recommend this item Sava as my favorate item Show this item's statistics Export Endnote File Google Scholar Similar articles in Google Scholar [Kazuo Murota]'s Articles CSDL cross search Similar articles in CSDL Cross Search [Kazuo Murota]‘s Articles Related Copyright Policies Null Social Bookmarking

 您对该条目有什么异议，请填写以下表单，管理员会尽快联系您。 内 容： Email： * 单位： 验证码： 刷新
 您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。 标 题： * 内 容： Email： * 验证码： 刷新