Generating and characterizing the perfect elimination orderings of a chordal graph

DOI10.1016/S0304-3975(03)00221-4zbMath1070.68116OpenAlexW1998427290WikidataQ55954628 ScholiaQ55954628MaRDI QIDQ1885018

Yanyan Li

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00221-4

zbMATH Keywords

Gray codeChordal graphAntimatroid 2-Processor schedulingClique treePerfect elimination ordering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (13)

A linear time algorithm to list the minimal separators of chordal graphs ⋮ Constant Time Enumeration by Amortization ⋮ Perfect elimination orderings for symmetric matrices ⋮ An efficient algorithm for counting Markov equivalent DAGs ⋮ Wishart exponential families on cones related to tridiagonal matrices ⋮ Counting the number of independent sets in chordal graphs ⋮ Two methods for the generation of chordal graphs ⋮ Learning discrete decomposable graphical models via constraint optimization ⋮ Enumeration of the perfect sequences of a chordal graph ⋮ Regularity of binomial edge ideals of chordal graphs ⋮ Bayesian model determination for multivariate ordinal and binary data ⋮ Oracles for vertex elimination orderings ⋮ Bayesian networks: the minimal triangulations of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• A note on lexicographic breadth first search for chordal graphs
• On rigid circuit graphs
• Some aspects of perfect elimination orderings in chordal graphs
• Greedoids
• Minimal vertex separators of chordal graphs
• Gray codes from antimatroids
• A characterisation of rigid circuit graphs
• Incidence matrices and interval graphs
• Optimal scheduling for two-processor systems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Representations of chordal graphs as subtrees of a tree
• Introduction to Greedoids
• Algorithmic Aspects of Vertex Elimination on Graphs
• Generating Linear Extensions Fast

This page was built for publication: Generating and characterizing the perfect elimination orderings of a chordal graph