|
|||||
|
|
Perfect elimination orderings for symmetric matrices |
|
| Authors: | Laurent Monique Tanigawa Shin-ichi |
| Institution: | 1.Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG, Amsterdam, The Netherlands ;2.Tilburg University, P.O. Box 90153, 5000 LE, Tilburg, The Netherlands ;3.Research Institute for Mathematical Sciences, Kyoto University, Kitashirakawa-Oiwaketyo, Sakyo-ku, Kyoto, 606-8502, Japan ; |
| Abstract: | 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |