Journal of the Ramanujan Mathematical Society

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Chordal Graphs with Specified Perfect Elimination Orderings


Affiliations
1 Department of Computer Science, Information Processing Centre, Birla Institute of Technology and Science, Pilani, Rajasthan 333 031, India
2 Department of Mathematics, Indian Institute of Technology, Kanpur-208 016, India
3 Stat-Math. Division, Indian Statistical Institute, Calcutta-700035, India
     

   Subscribe/Renew Journal


In this paper we characterize chordal graphs in which:

(i) Every perfect elimination ordering (PEO) can be generated by MCS algorithm.
(ii) Every PEO can be generated by LEX-BFS algorithm,
(iii) Every PEO can be generated by MCS algorithm as well as LEX-BFS algorithm, and
(iv) Every ordering generated by LEX-BFS algorithm can also be generated by MCS algorithm and vice versa.


User
Subscription Login to verify subscription
Notifications
Font Size

Abstract Views: 222

PDF Views: 0




  • Chordal Graphs with Specified Perfect Elimination Orderings

Abstract Views: 222  |  PDF Views: 0

Authors

B. S. Panda
Department of Computer Science, Information Processing Centre, Birla Institute of Technology and Science, Pilani, Rajasthan 333 031, India
S. P. Mohanty
Department of Mathematics, Indian Institute of Technology, Kanpur-208 016, India
S. B. Rao
Stat-Math. Division, Indian Statistical Institute, Calcutta-700035, India

Abstract


In this paper we characterize chordal graphs in which:

(i) Every perfect elimination ordering (PEO) can be generated by MCS algorithm.
(ii) Every PEO can be generated by LEX-BFS algorithm,
(iii) Every PEO can be generated by MCS algorithm as well as LEX-BFS algorithm, and
(iv) Every ordering generated by LEX-BFS algorithm can also be generated by MCS algorithm and vice versa.