Perfect elimination orderings for symmetric matrices

Monique Laurent, Shin-ichi Tanigawa

Research output: Contribution to journalArticleScientificpeer-review

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

Keywords

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

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

  • Research Output

    • 1 Working paper

    Perfect Elimination Orderings for Symmetric Matrices

    Laurent, M. & Tanigawa, S., 17 Apr 2017, Ithaca: Cornell University Library, 17 p. (arXiv; vol. 1706.05115).

    Research output: Working paperOther research output

    Open Access
  • Cite this