Generating and characterizing the perfect elimination orderings of a
chordal graph
L. Sunil
Chandran,
Indian Institute of Science,
Bangalore, India.
Louis Ibarra,
Department of Computer Science,
Simon Fraser University,
Canada
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Joe Sawada,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
We develop a constant time transposition "oracle" for the set of
perfect elimination orderings of chordal graphs. Using this oracle,
we can generate a Gray code of all perfect elimination orderings
in constant amortized time using known results about
antimatroids. Using clique trees, we show how the initialization
of the algorithm can be performed in linear time.
We also develop two new characterizations
of perfect elimination orderings: one in terms of
chordless paths, and the other in terms of minimal vertex separators.
-
The original title of this paper was Fast Generation of all Perfect
Elimination Orderings of a Chordal Graph.
-
The postscript file is 573,224 bytes.
-
Theoretical Computer Science, 307 (2003) 303-317;
special issue on
Random Generation of Combinatorial Objects.
-
An implementation of the algorithm is available
here (coming soon...).
-
Lou
is now a faculty member in the Department of Computer Science,
Telecommunications and Information Systems
at DePaul University in Chicago.
-
Joe is now a faculty member in the Department of
Computer Science at the University of Guelph.
Selected Citations to this paper:
-
Haggai Roitman, Avigdor Gal, and Louiqa Raschid,
A Dual Framework and Algorithms for Targeted Online Data Delivery,
IEEE Transactions on Knowledge and Data Engineering,
23 (2011) 5-21.
-
Y. Matsui, R. Uehara, and T. Uno,
Enumeration of the perfect sequences of a chordal graph,
Theoretical Computer Science, 411 (2009) 3635-3641.
-
Jing Kong and Yaokun Wu,
On economical set representations of graphs,
Discrete Mathematics and Theoretical Computer Science,
DMTCS 11 (2009) 71-96.
-
L. Markenzon, O. Vernet, and P.R.C. Pereira,
A compact code for k-trees,
Pesquisa Operacional, 29 (2009) 493-502.
-
Emily L. Webb and Jonathan J. Forster,
Bayesian model determination for multivariate ordinal and binary data, Computational Statistics & Data Analysis, 52 (2008) 2632-2649.
-
Yasuko Matsui, Ryuhei Uehara, and Takeaki Uno,
Enumeration of Perfect Sequences of Chordal Graph,
19th Annual International Symposium on Algorithms and Computation
(ISAAC 2008), LNCS 5369 (2008) 859-870.
-
Lilian Markenzon, Oswaldo Vernet and Luiz Henrique Araujo
Two methods for the generation of chordal graphs,
Annals of Operations Research, 157 (2007) 47-60.
-
Masashi Kiyomi, Shuji Kijima, and Takeaki Uno,
Listing Chordal Graphs and Interval Graphs,
Proceedings of 32st International Workshop on Graph-Theoretic
Concepts in Computer Science (WG 2006),
Lecture Notes in Computer Science 4271 (2006) 68-77.
-
Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara,
Linear-time counting algorithms for independent
sets in chordal graphs,
Proceedings of 31st International Workshop on Graph-Theoretic
Concepts in Computer Science (WG 2005),
Lecture Notes in Computer Science 3787 (2005) 433-444.
-
Pinar Heggernes and Yngve Villanger,
Simple and Efficient Modifications of Elimination Orderings,
Proceedings PARA 2004 - Workshop on State-of-the-Art in Scientific Computing,
Lyngby, Denmark, June 2004.
Springer Verlag, Lecture Notes in Computer Science 3732, pages 788 - 797.
Back to list of publications.