TY - GEN
T1 - A linear time algorithm for determining almost bipartite graphs
AU - He, Dayu
AU - He, Xin
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - A graph G = (V,E) is called almost bipartite if G is not bipartite, but there exists a vertex v ∈ V such that G−{v} is bipartite. We consider the problem of testing if G is almost bipartite or not. This problem arises from the study on the k-arch layout problem. It is known that, given a graph G and an integer k ≥ 2, it is NP-complete to determine if G has a k-arch layout. On the other hand, G has a 1-arch layout if and only if G is almost bipartite [3]. It is straightforward to test if G is almost bipartite in O(n(n+m)) time by using depth first search. In this paper, we present a simple linear time algorithm for solving this problem. The efficiency of the algorithm is achieved by sophisticated applications of depth first search tree and the study of the structure of such graphs.
AB - A graph G = (V,E) is called almost bipartite if G is not bipartite, but there exists a vertex v ∈ V such that G−{v} is bipartite. We consider the problem of testing if G is almost bipartite or not. This problem arises from the study on the k-arch layout problem. It is known that, given a graph G and an integer k ≥ 2, it is NP-complete to determine if G has a k-arch layout. On the other hand, G has a 1-arch layout if and only if G is almost bipartite [3]. It is straightforward to test if G is almost bipartite in O(n(n+m)) time by using depth first search. In this paper, we present a simple linear time algorithm for solving this problem. The efficiency of the algorithm is achieved by sophisticated applications of depth first search tree and the study of the structure of such graphs.
UR - https://www.scopus.com/pages/publications/84929616359
U2 - 10.1007/978-3-319-17142-5_15
DO - 10.1007/978-3-319-17142-5_15
M3 - Conference contribution
AN - SCOPUS:84929616359
T3 - Lecture Notes in Computer Science
SP - 164
EP - 176
BT - Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings
A2 - Jain, Rahul
A2 - Jain, Sanjay
A2 - Stephan, Frank
PB - Springer Verlag
T2 - 12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015
Y2 - 18 May 2015 through 20 May 2015
ER -