Research Output per year
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.
- chordal graph
- perfect elimination ordering
- unit interval graph
- shortest path metric
- robinson matrix
Laurent, M. & Tanigawa, S., 17 Apr 2017, Ithaca: Cornell University Library, 17 p. (arXiv; vol. 1706.05115).
Research output: Working paper › Other research output