DSpace
 

EPrints@IIT Delhi >
Faculty Research Publicatons  >
Mathematics >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/1204

Title: A linear time recognition algorithm for proper interval graphs
Authors: Panda, B S
Das, Sajal K
Keywords: Hamiltonian cycle
Chordal graphs
Interval graphs
Proper interval graphs
Algorithms
Issue Date: 2003
Citation: Information Processing Letters, 87(3), 153-161
Abstract: We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian cycle of G.
URI: http://eprint.iitd.ac.in/dspace/handle/2074/1204
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
pandalin2003.pdf149.46 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback