Geodesic
Eigenvalues and the max-cut problem
Czechoslovak Mathematical Journal, Tome 40 (1990) no. 2, pp. 343-352
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

DOI : 10.21136/CMJ.1990.102386
Classification : 05C50, 90B10, 90C27, 90C35 
@article{10_21136_CMJ_1990_102386,
     author = {Mohar, Bojan and Poljak, Svatopluk},
     title = {Eigenvalues and the max-cut problem},
     journal = {Czechoslovak Mathematical Journal},
     pages = {343--352},
     year = {1990},
     volume = {40},
     number = {2},
     doi = {10.21136/CMJ.1990.102386},
     mrnumber = {1046300},
     zbl = {0724.05046},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.1990.102386/}
}
TY  - JOUR
AU  - Mohar, Bojan
AU  - Poljak, Svatopluk
TI  - Eigenvalues and the max-cut problem
JO  - Czechoslovak Mathematical Journal
PY  - 1990
SP  - 343
EP  - 352
VL  - 40
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.1990.102386/
DO  - 10.21136/CMJ.1990.102386
LA  - en
ID  - 10_21136_CMJ_1990_102386
ER  - 
%0 Journal Article
%A Mohar, Bojan
%A Poljak, Svatopluk
%T Eigenvalues and the max-cut problem
%J Czechoslovak Mathematical Journal
%D 1990
%P 343-352
%V 40
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.1990.102386/
%R 10.21136/CMJ.1990.102386
%G en
%F 10_21136_CMJ_1990_102386
Mohar, Bojan; Poljak, Svatopluk. Eigenvalues and the max-cut problem. Czechoslovak Mathematical Journal, Tome 40 (1990) no. 2, pp. 343-352. doi: 10.21136/CMJ.1990.102386

[A] N. Alon: Eigenvalues and expanders. Combinatorica 6, (1986) 83-96. | DOI | MR | Zbl

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

[AnM] W. N. Anderson T. D. Morley: Eigenvalues of the Laplacian of a graph. Lin. Multilin. Algebra 18 (1985) 141-145. | DOI | MR

[B] F. Barahona: The max-cut problem in graphs not contractible to K5. Oper. Res. Lett. 2 (1983) 107-111. | DOI | MR

[BGJR] 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. | DOI

[CDS] 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.

[F] M. Fiedler: Algebraic connectivity of graphs. Czechoslovak Math. J. 23 (98) (1973) 298-305. | MR | Zbl

[GN] 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. | DOI | MR

[GP] M. Grötschel, W. R. Pulleyblank: Weakly bipartite graphs and the max-cut problem. Oper. Res.Lett. / (1981) 23-27. | DOI | MR

[H] F. Hadlock: Finding a maximum cut of a planar graph in polynomial time. SIAM J. on Comp. 4 (1975) 221-225. | DOI | MR | Zbl

[Ka] 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. | MR

[Ke] 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). | MR

[L] P. Lankaster: Theory of Matrices. Acad. Press, New York-London 1969. | MR

[Lo] L. Lovász: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory 25 (1979) 1-7. | DOI | MR

[LPS] A. Lubotzky R. Phillips, P. Sarnak: Ramanujan graphs. Combinatorica, 8 (1988) 261-277. | DOI | MR

[Ml] B. Mohar: Isoperimetric numbers of graphs. J. Comb. Th. B, to appear. | MR | Zbl

[M2] B. Mohar: The Laplacian spectrum of graphs. submitted. | Zbl

[NP] 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. | DOI | MR

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

[PT] S. Poljak, Z. Tuza: Maximum bipartite subgraphs of Kneser graphs. Graphs and Combinatorics, 3 (1987) 191-199. | DOI | MR | Zbl

[PT1] S. Poljak, D. Turzík: A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound. Discrete Math. 58 (1986) 99-104. | DOI | MR

[PT2] S. Poljak, D. Turzík: Maximum bipartite subgraphs of circulants. submitted.

[T] R. M. Tanner: Explicit concentrators from generalized n-gons. SIAM J. Alg. Disc. Meth. 5 (1984) 287-293. | DOI | MR | Zbl

Cité par Sources :