Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs

Authors

  • Mihai Talmaciu Department of Mathematics and Informatics, "Vasile Alecsandri" University of Bacău
  • Elena Nechita Department of Mathematics and Informatics, "Vasile Alecsandri" University of Bacău
  • Barna Iantovics Department of Informatics, "Petru Maior" University of Tărgu Mureş

Keywords:

Bipartite chain graphs, weakly decomposition, recognition algorithms, combinatorial optimization algorithms

Abstract

In this paper we give a recognition algorithm in O(n(n+m)) time for bipartite chain graphs, and directly calculate the density of such graphs. For their stability number and domination number, we give algorithms comparable to the existing ones. We point out some applications of bipartite chain graphs in chemistry and approach the Minimum Chain Completion problem.

Downloads

Download data is not yet available.

Downloads

Published

2013-05-23

How to Cite

Talmaciu, M., Nechita, E., & Iantovics, B. (2013). Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs. Computing and Informatics, 32(2), 313–329. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/1623

Issue

Vol. 32 No. 2 (2013): Computing and Informatics

Section

Articles