Recognizing line-polar bipartite graphs in time O(n)
Discrete Applied Mathematics, cilt.158, sa.15, ss.1593-1598, 2010 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 158 Sayı: 15
- Basım Tarihi: 2010
- Doi Numarası: 10.1016/j.dam.2010.05.019
- Dergi Adı: Discrete Applied Mathematics
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.1593-1598
- Anahtar Kelimeler: Line-polar graph, Linear time recognition algorithm, Polar graph
- Boğaziçi Üniversitesi Adresli: Evet
Özet
A graph is polar if the vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite graphs, cobipartite graphs and split graphs. Recognizing polar graphs is an NP-complete problem in general, and thus it is of interest to restrict the problem to special classes of graphs. Cographs and chordal graphs are among those whose polarity can be recognized in polynomial time. The line-graphs of bipartite graphs are another class of graphs whose polarity has been characterized recently in terms of forbidden subgraphs, but no polynomial time algorithm is given. In this paper, we present an O(n) algorithm which decides whether the line-graph of an input bipartite graph is polar and constructs a polar partition when one exists. © 2010 Elsevier B.V. All rights reserved.