Perfect elimination orderings for symmetric matrices

DOI10.1007/s11590-017-1213-yzbMath1442.05080DBLPjournals/ol/LaurentT20arXiv1704.05115OpenAlexW3100228149WikidataQ59607064 ScholiaQ59607064MaRDI QIDQ2174877

Shin-ichi Tanigawa, Monique Laurent

Publication date: 27 April 2020

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1704.05115

zbMATH Keywords

chordal graphultrametricunit interval graphRobinson matrixperfect elimination orderingshortest path metric

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (05C99) Signed and weighted graphs (05C22)

Cites Work

• A new LBFS-based algorithm for cocomparability graph recognition
• A structural characterization for certifying Robinsonian matrices
• On rigid circuit graphs
• Positive definite completions of partial Hermitian matrices
• An optimal greedy heuristic to color interval graphs
• LexBFS-orderings and powers of chordal graphs
• Perfect elimination orderings of chordal powers of graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Generating and characterizing the perfect elimination orderings of a chordal graph
• Incidence matrices and interval graphs
• The Roberts characterization of proper and unit interval graphs
• Oracles for vertex elimination orderings
• Domination on Cocomparability Graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Convexity in Graphs and Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• On Distance-Preserving and Domination Elimination Orderings
• Dually Chordal Graphs
• Seriation and matrix reordering methods: An historical overview
• Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Perfect elimination orderings for symmetric matrices