Minimum average distance clique trees

DOI10.1137/15M1021052MaRDI QIDQ2947438zbMATH OpenOpenAlexFDO

Authors S. J. Xu, Rob Gysel, Dan Gusfield

Publication date 23 September 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/15m1021052

zbMATH Keywords

chordal graphsclique treesminimum average distancephylogeneticstriangulated graphsWiener index

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Problems related to evolution (92D15)

Recommendations

• scientific article; zbMATH DE number 751126
• Reduced clique graphs of chordal graphs
• scientific article; zbMATH DE number 554762
• On the tree representation of chordal graphs
• An efficient representation of chordal graphs

Cites work

• A characterisation of rigid circuit graphs
• A characterization for a set of partial partitions to define an \(X\)-tree
• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Algorithmic graph theory and perfect graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
• Distance in graphs
• Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
• Generalizing the splits equivalence theorem and four gamete condition: Perfect phylogeny on three-state characters
• Generating the maximum spanning trees of a weighted graph
• scientific article; zbMATH DE number 48812 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 751126 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Identifying phylogenetic trees
• Incidence matrices and interval graphs
• Modeling and Reasoning with Bayesian Networks
• On rigid circuit graphs
• Power of Natural Semijoins
• Rank inequalities for chordal graphs
• Representations of chordal graphs as subtrees of a tree
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• The complexity of reconstructing trees from qualitative characters and subtrees
• The complexity of the network design problem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The leafage of a chordal graph
• Triangulated graphs and the elimination process
• Wiener index of hexagonal systems
• Wiener index of trees: Theory and applications

Cited in

(6)

• On the maximum value of the eccentric distance sums of cubic transitive graphs
• Moplex orderings generated by the LexDFs algorithm
• A survey of the all-pairs shortest paths problem and its variants in graphs
• Minimum Average Distance Triangulations
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 751126 (Why is no real title available?)

This page was built for publication: Minimum average distance clique trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947438)