Perfect elimination orderings for symmetric matrices
From MaRDI portal
Publication:2174877
DOI10.1007/s11590-017-1213-yzbMath1442.05080arXiv1704.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
chordal graphultrametricunit interval graphRobinson matrixperfect elimination orderingshortest path metric
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (05C99) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
