Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs
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ş
Computing and Informatics, Tome 31 (2013) no. 6, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2013-05-23
Classification:  Bipartite chain graphs, weakly decomposition, recognition algorithms, combinatorial optimization algorithms 
@article{cai1623,
     author = {Mihai Talmaciu; Department of Mathematics and Informatics, "Vasile Alecsandri" University of Bac\u au and Elena Nechita; Department of Mathematics and Informatics, "Vasile Alecsandri" University of Bac\u au and Barna Iantovics; Department of Informatics, "Petru Maior" University of T\u argu Mure\c s},
     title = {Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs},
     journal = {Computing and Informatics},
     volume = {31},
     number = {6},
     year = {2013},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai1623}
}

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ş. Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs. Computing and Informatics, Tome 31 (2013) no. 6, . http://gdmltest.u-ga.fr/item/cai1623/