Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs

Mihai Talmaciu; Elena Nechita; Barna Iantovics

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.

Keywords

Cite this article

@article{cai-110191,
  author  = {Mihai Talmaciu and Elena Nechita and Barna Iantovics},
  title   = {Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs},
  journal = {Computing and Informatics},
  volume  = {32},
  number  = {2},
  pages   = {313--329},
  year    = {2013},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2013/2/recognition-and-combinatorial-optimization-algorithms-for-bipartite-chain-graphs/}
}

Download .bib

TY  - JOUR
AU  - Mihai Talmaciu
AU  - Elena Nechita
AU  - Barna Iantovics
TI  - Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs
JO  - Computing and Informatics
VL  - 32
IS  - 2
SP  - 313
EP  - 329
PY  - 2013
SN  - 1335-9150
UR  - https://cai.type.sk/content/2013/2/recognition-and-combinatorial-optimization-algorithms-for-bipartite-chain-graphs/
KW  - Bipartite chain graphs
KW  - weakly decomposition
KW  - recognition algorithms
KW  - combinatorial optimization algorithms
ER  -

Download .ris

Talmaciu, M., Nechita, E., & Iantovics, B. (2013). Recognition and Combinatorial Optimization Algorithms for Bipartite Chain Graphs. Computing and Informatics, 32(2), 313–329. https://cai.type.sk/content/2013/2/recognition-and-combinatorial-optimization-algorithms-for-bipartite-chain-graphs/

Download .txt