Perfect elimination orderings for symmetric matrices

Monique Laurent, Shin-ichi Tanigawa

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Pages (from-to)339-353
JournalOptimization Letters
Issue number2
Publication statusPublished - Mar 2020


  • chordal graph
  • perfect elimination ordering
  • unit interval graph
  • ultrametric
  • shortest path metric
  • robinson matrix


Dive into the research topics of 'Perfect elimination orderings for symmetric matrices'. Together they form a unique fingerprint.

Cite this