Eigenvalues and the max-cut problem
Mohar, Bojan ; Poljak, Svatopluk
Czechoslovak Mathematical Journal, Tome 40 (1990), p. 343-352 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)
Publié le : 1990-01-01
Classification:  05C50,  90B10,  90C27,  90C35 
@article{102386,
     author = {Bojan Mohar and Svatopluk Poljak},
     title = {Eigenvalues and the max-cut problem},
     journal = {Czechoslovak Mathematical Journal},
     volume = {40},
     year = {1990},
     pages = {343-352},
     zbl = {0724.05046},
     mrnumber = {1046300},
     language = {en},
     url = {http://dml.mathdoc.fr/item/102386}
}

Mohar, Bojan; Poljak, Svatopluk. Eigenvalues and the max-cut problem. Czechoslovak Mathematical Journal, Tome 40 (1990) pp. 343-352. http://gdmltest.u-ga.fr/item/102386/

N. Alon Eigenvalues and expanders, Combinatorica 6, (1986) 83-96. (1986) | Article | MR 0875835 | Zbl 0661.05053

N. Alon V. D. Milman $\lambda_1$Xx, isoperimetric inequalities for graphs and superconcentrators, J. Comb. Th. B 38 (1985) 73-88. (1985) | Article | MR 0782626

W. N. Anderson T. D. Morley Eigenvalues of the Laplacian of a graph, Lin. Multilin. Algebra 18 (1985) 141-145. (1985) | Article | MR 0817657

F. Barahona The max-cut problem in graphs not contractible to K5, Oper. Res. Lett. 2 (1983) 107-111. (1983) | Article | MR 0717742

F. Barahona M. Grötschel M. Jünger G. Reinelt An application of combinatorial optimization to statistical physcis and circuit layout design, Oper. Res. 36 (1988) 493-513. (1988) | Article

D. M. Cvetkovic M. Doob; And H. Sachs Spectra of graphs - Theory and applications, VEB Deutscher Verlag der Wiss. Berlin 1979/Acad. Press, N.Y. 1979. (1979)

M. Fiedler Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (98) (1973) 298-305. (1973) | MR 0318007 | Zbl 0265.05119

M. Grötschel; G. L. Nemhauser A polynomial algorithm for the max-cut problem on graphs without long odd cycles, Math. Programming 29 (1984) 28-40. (1984) | Article | MR 0740503

M. Grötschel; W. R. Pulleyblank Weakly bipartite graphs and the max-cut problem, Oper. Res.Lett. / (1981) 23-27. (1981) | Article | MR 0643056

F. Hadlock Finding a maximum cut of a planar graph in polynomial time, SIAM J. on Comp. 4 (1975) 221-225. (1975) | Article | MR 0379290 | Zbl 0321.05120

R. M. Karp Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller, J. W. Thatcher (eds.), Plenum Press, New York 1972, pp. 85-103. (1972) | MR 0378476

A. K. Kel'Mans Properties of the characteristic polynomial of a graph, "Kibernetiky - na službu kommunizmu" vol. 4, Energija, Moskva-Leningrad, 1967, pp. 27-41 (in Russian). (1967) | MR 0392633

P. Lankaster Theory of Matrices, Acad. Press, New York-London 1969. (1969) | MR 0245579

L. Lovász On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979) 1-7. (1979) | Article | MR 0514926

A. Lubotzky R. Phillips; P. Sarnak Ramanujan graphs, Combinatorica, 8 (1988) 261-277. (1988) | Article | MR 0963118

B. Mohar Isoperimetric numbers of graphs, J. Comb. Th. B, to appear. | MR 1026065 | Zbl 0719.05042

B. Mohar The Laplacian spectrum of graphs, submitted. | Zbl 0840.05059

J. Nešetřil; S. Poljak A remark on max-cut problem with an application to digital-analogue convertors, Oper. Res. Lett. 4 (1986) 289-291. (1986) | Article | MR 0836264

G. I. Orlova; Y. G. Dorfman Finding the maximal cut in a graph, Engrg. Cybernetics 10 (1972) 502-506. (1972) | MR 0329962

S. Poljak; Z. Tuza Maximum bipartite subgraphs of Kneser graphs, Graphs and Combinatorics, 3 (1987) 191-199. (1987) | Article | MR 0932133 | Zbl 0674.05064

S. Poljak; D. Turzík A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound, Discrete Math. 58 (1986) 99-104. (1986) | Article | MR 0820844

S. Poljak; D. Turzík Maximum bipartite subgraphs of circulants, submitted.

R. M. Tanner Explicit concentrators from generalized n-gons, SIAM J. Alg. Disc. Meth. 5 (1984) 287-293. (1984) | Article | MR 0752035 | Zbl 0554.05045