Geodesic
A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
Canadian journal of mathematics, Tome 34 (1982) no. 3, pp. 519-524

Voir la notice de l'article provenant de la source Cambridge University Press

Let G be a symmetric connected graph without loops. Denote by b(G) the maximum number of edges in a bipartite subgraph of G. Determination of b(G) is polynomial for planar graphs ([6], [8]); in general it is an NP-complete problem ([5]). Edwards in [1], [2] found some estimates of b(G) which give, in particular, for a connected graph G of n vertices and m edges, where and {x} denotes the smallest integer ≧ x.We give an 0(V 3) algorithm which for a given graph constructs a bipartite subgraph B with at least f(m, n) edges, yielding a short proof of Edwards’ result.Further, we consider similar methods for obtaining some estimates for a particular case of the satisfiability problem. Let Φ be a Boolean formula of variables x 1, ..., x n. 
Poljak, Svatopluk; Turzík, Daniel. A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem. Canadian journal of mathematics, Tome 34 (1982) no. 3, pp. 519-524. doi: 10.4153/CJM-1982-036-8
@article{10_4153_CJM_1982_036_8,
     author = {Poljak, Svatopluk and Turz{\'\i}k, Daniel},
     title = {A {Polynomial} {Algorithm} for {Constructing} a {Large} {Bipartite} {Subgraph,} with an {Application} to a {Satisfiability} {Problem}},
     journal = {Canadian journal of mathematics},
     pages = {519--524},
     year = {1982},
     volume = {34},
     number = {3},
     doi = {10.4153/CJM-1982-036-8},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-036-8/}
}
TY  - JOUR
AU  - Poljak, Svatopluk
AU  - Turzík, Daniel
TI  - A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
JO  - Canadian journal of mathematics
PY  - 1982
SP  - 519
EP  - 524
VL  - 34
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-036-8/
DO  - 10.4153/CJM-1982-036-8
ID  - 10_4153_CJM_1982_036_8
ER  - 
%0 Journal Article
%A Poljak, Svatopluk
%A Turzík, Daniel
%T A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
%J Canadian journal of mathematics
%D 1982
%P 519-524
%V 34
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-036-8/
%R 10.4153/CJM-1982-036-8
%F 10_4153_CJM_1982_036_8

[1] 1. Edwards, C. S., Some extremal properties of bipartite subgraphs, Can. J. Math. 25 (1973), 475–485. Google Scholar

[2] 2. Edwards, C. S., An improved lower bound for the number of edges in a largest bipartite subgraph, in: Recent advances in graph theory (Academia, Prague), 1975–167. Google Scholar

[3] 3. S. A., Cook, The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing, Association for Computing Machinery, New York (1970), 151–158. Google Scholar

[4] 4. Davis, M. and Putnam, H., A computing procedure for quantification theory, JACM 7 (1960), 201–215. Google Scholar

[5] 5. Garey, M. R., Johnson, D. S. and Stockmayer, L., Some simplified NP-complete graph problems, Theoretical Computer S ience 1 (1976), 237–267. Google Scholar

[6] 6. Hadlock, R. O., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comp. 4 (1975), 221–225. Google Scholar

[7] 7. Harary, F., Graph theory (Addison Wesley, Reading, Massachusetts, 1969. Google Scholar

[8] 8. Orlova, G. I. and Dorfman, Y. G., Finding the maximum cut in a graph, Engrg. Cybernetics 10 (1972), 502–506. Google Scholar

[9] 9. Paton, K., An algorithm for the blocks and cutnodes of a graph, Comm. ACM 14 (1971), 468–476. Google Scholar

[10] 10. Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput. 1 (1972), 146–160. Google Scholar

[11] 11. Tarjan, R., An efficient planarity algorithm, Thesis, Stanford University (1971). Google Scholar

Cité par Sources :