Some aspects of perfect elimination orderings in chordal graphs

DOI10.1016/0166-218X(84)90008-8zbMath0537.05069MaRDI QIDQ792351

Douglas R. Shier

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

chordal graphsperfect elimination orderingsquasiconcave functions

Mathematics Subject Classification ID

Graph theory (05C99) Convolutional codes (94B10)

Related Items

A linear time algorithm to list the minimal separators of chordal graphs, Generating and characterizing the perfect elimination orderings of a chordal graph, Matrices with chordal inverse zero-patterns, New linear time algorithms for generating perfect elimination orderings of chordal graphs, Coloring problem of signed interval graphs, Graph searches and their end vertices, Maximal chordal subgraphs, Separability generalizes Dirac's theorem, A general label search to investigate classical graph search algorithms, A tie-break model for graph search, On domination elimination orderings and domination graphs, Hardness and algorithms of equitable tree-coloring problem in chordal graphs, Some aspects of the semi-perfect elimination, Antimatroids and balanced pairs, Peakless functions on graphs, On the Power of Graph Searching for Cocomparability Graphs, Perfect elimination orderings of chordal powers of graphs, The Recognition Problem of Graph Search Trees, Bayesian networks: the minimal triangulations of a graph, A Helly theorem for convexity in graphs, Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution, Extremities and orderings defined by generalized graph search algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• A characterisation of rigid circuit graphs
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Representation of a finite graph by a set of intervals on the real line
• Scheduling Interval-Ordered Tasks
• Polynomially bounded algorithms for locatingp-centers on a tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Equivalence in nonlinear programming
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph