Abstract
We consider the following problem, called Relative Minimal Elimination Ordering. Given a graph G = (V, E) which is a subgraph of the chordal graph G′ = (V, E′); compute an inclusion minimal chordal graph G" = (V, E"), such that \(E \subseteq E'' \subseteq E'\). We show that this can be done in O(nm) time. This extends the results of [2]. The algorithm is also simpler and is based only on well known results on chordal graphs.
e-mail: dahlhaus@informatik.uni-koeln.de
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Reference
A. Agrawal, P. Klein, R. Ravi, Cutting Down on Fill-in Using Nested Dissection, in Sparse Matrix Computations: Graph Theory Issues and Algorithms, A. George, J. Gilbert, J.W.-H. Liu ed., IMA Volumes in Mathematics and its Applications, Vol. 56, Springer Verlag, 1993, pp. 31–55.
J. Blair, P. Heggernes, J.A. Telle, Making an Arbitrary Filled Graph Minimal by Removing Fill Edges, Algorithm Theory.-SWAT96, R. Karlsson, A. Lingas ed., LLNCS 1097, pp. 173–184.
P. Bunemann, A Characterization of Rigid Circuit Graphs, Discrete Mathematics 9 (1974), pp. 205–212.
E. Dahlhaus, Fast parallel algorithm for the single link heuristics of hierarchical clustering, Proceedings of the fourth IEEE Symposium on Parallel and Distributed Processing (1992), pp. 184–186.
E. Dahlhaus, Efficient Parallel Algorithms on Chordal Graphs with a Sparse Tree Representation, Proceedings of the 27-th Annual Hawaii International Conference on System Sciences, Vol. II (1994), pp. 150–158.
Elias Dahlhaus, Sequential and Parallel Algorithms on Compactly Represented Chordal and Strongly Chordal Graphs, STAGS 97, R. Reischuk, M. Morvan ed., LLNCS 1200 (1997), pp. 487–498.
Elias Dahlhaus, Marek Karpinski, An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph, Theoretical Computer Science 134 (1994), pp. 493–528.
M. Farber, Characterizations of Strongly Chordal Graphs, Discrete Mathematics 43 (1983), pp. 173–189.
F. Gavril, The Intersection Graphs of Subtrees in Trees Are Exactly the Chordal Graphs, Journal of Combinatorial Theory Series B, vol. 16 (1974), pp. 47–56.
A. George, J.W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall Inc., Englewood Cliffs, NJ, 1981.
J. Gilbert, H. Hafsteinsson, Parallel Solution of Sparse Linear Systems, SWAT 88
D. Rose, Triangulated Graphs and the Elimination Process, Journal of Mathematical Analysis and Applications 32 (1970), pp. 597–609.
D. Rose, R. Tarjan, G. Lueker, Algorithmic Aspects on Vertex Elimination on Graphs, SIAM Journal on Computing 5 (1976), pp. 266–283.
Y. Shiloach, U. Vishkin, An O(log n) Parallel Connectivity Algorithm, Journal of Algorithms 3 (1982), pp. 57–67.
R. Tarjan, Efficiency of a Good but not Linear Set Union Algorithm, Journal of the ACM 22 (1975), pp. 215–225.
R. Tarjan, M. Yannakakis, Simple Linear Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM Journal on Computing 13 (1984), pp. 566–579.
Addendum: SIAM Journal on Computing 14 (1985), pp. 254–255.
M. Yannakakis, Computing the Minimum Fill-in is NP-complete, SIAM Journal on Algebraic and Discrete Methods 2 (1981), pp. 77–79.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dahlhaus, D. (1997). Minimal elimination ordering inside a given chordal graph. In: Möhring, R.H. (eds) Graph-Theoretic Concepts in Computer Science. WG 1997. Lecture Notes in Computer Science, vol 1335. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0024494
Download citation
DOI: https://doi.org/10.1007/BFb0024494
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63757-8
Online ISBN: 978-3-540-69643-8
eBook Packages: Springer Book Archive