New Characterizations of Proper Interval Bigraphs and Proper Circular Arc Bigraphs

详细信息    查看全文

• 作者：Ashok Kumar Das (17)
  Ritapa Chakraborty (17)
  
• 关键词：interval bigraphs ; circular arc bigraphs ; proper interval bigraphs ; proper circular arc bigraphs ; linear ordering
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8959
• 期：1
• 页码：117-125
• 全文大小：194 KB
• 参考文献：1. Basu, A., Das, S., Ghosh, S., Sen, M.: Circular arc bigraphs and its subclasses. J. of Graph Theory (73), 361鈥?76 (2013)
  2. Brown, D.E., Lundgren, J.R.: Characterization for unit interval bigraphs. In: Proceedings of the Forty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Number. 206, 517 (2010)
  3. Brown, D.E., Lundgren, J.R., Flink, S.C.: Characterization of interval bigraphs and unit interval bigraphs. Congress Number (2002)
  4. Das, A.K., Chakraborty, R.: New characterization of proper interval bigraphs. Accepted for Publication in International Journal of Graphs and Combinatorics 12(1) (June 2015)
  5. Das, A.K., Das, S., Sen, M.K.: Forbidden substructure of interval (bi/di) graphs. Submitted to Discrete Math. (2014)
  6. Deng, X., Hell, P., Huang, J.: Linear time representation of proper circular arc graphs and proper interval graphs. SIAM J. Comput.聽25, 390鈥?03 (1996) CrossRef
  7. Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Annals of Discrete Mathematics (2014)
  8. Hell, P., Huang, J.: Certifying LexBFS recognition algorithm for proper interval graphs and proper interval bigraphs. SIAM J. Discrete Math.聽18(3), 554鈥?70 (2004) CrossRef
  9. Hell, P., Huang, J.: Interval bigraphs and circular arc graphs. J. of Graph Theory聽(46), 313鈥?27 (2004)
  10. Lin, I.J., Sen, M.K., West, D.B.: Class of interval digraphs and 0, 1- matrices. Congressus Num.聽125, 201鈥?09 (1997)
  11. McConnell, R.M.: Linear time recognition of circular arc graphs. Algorithms聽37(2), 93鈥?47 (2003) CrossRef
  12. Sanyal, B.K., Sen, M.K.: New characterization of digraphs represented by intervals. J. of Graph Theory聽22, 297鈥?03 (1996) CrossRef
  13. Sen, M., Das, S., West, D.B.: Circular arc digraphs: A characterization. J.of Graph Theory聽13, 581鈥?92 (1989) CrossRef
  14. Sen, M., Das, S., Roy, A.B., West, D.B.: An analogue of interval graphs. J.of Graph Theory聽13, 189鈥?02 (1989) CrossRef
  15. Sen, M., Sanyal, B.K.: Indifference Digraphs: A generalization of indifference graphs and semiorders. SIAM J. Discrete Math.聽7, 157鈥?65 (1994) CrossRef
  16. Sen, M., Sanyal, B.K., West, D.B.: Representing digraphs using intervals or circular arcs. Discrete Math.聽147, 235鈥?45 (1995) CrossRef
  17. Spinard, J., Brandstad, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Math.聽18, 279鈥?92 (1987) CrossRef
  18. Steiner, G.: The recognition of indifference digraphs and generalized Semiorders. J. of Graph Theory聽21(2), 235鈥?41 (1996) CrossRef
  
• 作者单位：Ashok Kumar Das (17)
  Ritapa Chakraborty (17)
  
  17. Department of Pure Mathematics, University of Calcutta, 35, Ballygunge Circular Road, Kolkata, 700019, India
  
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-14974-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

An interval bigraph B is a proper interval bigraph if there is an interval representation of B such that no interval of the same partite set is properly contained in the other. Similarly a circular arc bigraph B is a proper circular arc bigraph if there is a circular arc representation of B such that no arc of the same partite set is properly contained in the other. In this paper, we characterize proper interval bigraphs and proper circular arc bigraphs using two linear orderings of their vertex set.