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
JournalOptimization Letters
DOIs
Publication statusE-pub ahead of print - Nov 2017

Fingerprint

Symmetric matrix
Elimination
Structured Matrices
Chordal Graphs
Weighted Graph
Substructure
Graph in graph theory
Monotone
Cycle
Vertex of a graph

Keywords

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

Cite this

@article{fb42cb6621f249558af4e9a4dfe76eab,
title = "Perfect elimination orderings for symmetric matrices",
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 = "chordal graph, perfect elimination ordering, unit interval graph, ultrametric, shortest path metric, robinson matrix",
author = "Monique Laurent and Shin-ichi Tanigawa",
year = "2017",
month = "11",
doi = "10.1007/s11590-017-1213-y",
language = "English",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",

}

Perfect elimination orderings for symmetric matrices. / Laurent, Monique; Tanigawa, Shin-ichi.

In: Optimization Letters, 11.2017.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Perfect elimination orderings for symmetric matrices

AU - Laurent, Monique

AU - Tanigawa, Shin-ichi

PY - 2017/11

Y1 - 2017/11

N2 - 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.

AB - 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.

KW - chordal graph

KW - perfect elimination ordering

KW - unit interval graph

KW - ultrametric

KW - shortest path metric

KW - robinson matrix

U2 - 10.1007/s11590-017-1213-y

DO - 10.1007/s11590-017-1213-y

M3 - Article

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

ER -