Perfect elimination orderings for symmetric matrices
Perfect elimination orderings for symmetric matrices
复制标题
对称矩阵的完美消除排序
DOI：
10.1007/s11590-017-1213-y
复制
发表时间：
2018
影响因子：
1.6
通讯作者：
Monique Laurent and Shin-ichi Tanigawa
中科院分区：
文献类型：
--
作者：
Sayaka Kamei;Tomoko Izumi;Yukiko Yamauchi,;Matthew de Brecht;Monique Laurent and Shin-ichi Tanigawa
通过将图的完全消去排序的概念推广到加权图或矩阵，引入了一类新的结构对称矩阵。这提供了一个共同的框架，捕捉和弦图，罗宾逊矩阵和超度量的单调族的共同顶点消除顺序。在图中推广无弦循环的禁忌子结构方面，给出了具有完全消去序的矩阵的结构表征。
We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs.