| Title:
|
Eigenvalues and the max-cut problem (English) |
| Author:
|
Mohar, Bojan |
| Author:
|
Poljak, Svatopluk |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
40 |
| Issue:
|
2 |
| Year:
|
1990 |
| Pages:
|
343-352 |
| . |
| Category:
|
math |
| . |
| MSC:
|
05C50 |
| MSC:
|
90B10 |
| MSC:
|
90C27 |
| MSC:
|
90C35 |
| idZBL:
|
Zbl 0724.05046 |
| idMR:
|
MR1046300 |
| DOI:
|
10.21136/CMJ.1990.102386 |
| . |
| Date available:
|
2008-06-09T15:33:18Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/102386 |
| . |
| Reference:
|
[A] N. Alon: Eigenvalues and expanders.Combinatorica 6, (1986) 83-96. Zbl 0661.05053, MR 0875835, 10.1007/BF02579166 |
| Reference:
|
[AM] N. Alon V. D. Milman: $\lambda_1$Xx, isoperimetric inequalities for graphs and superconcentrators.J. Comb. Th. B 38 (1985) 73-88. MR 0782626, 10.1016/0095-8956(85)90092-9 |
| Reference:
|
[AnM] W. N. Anderson T. D. Morley: Eigenvalues of the Laplacian of a graph.Lin. Multilin. Algebra 18 (1985) 141-145. MR 0817657, 10.1080/03081088508817681 |
| Reference:
|
[B] F. Barahona: The max-cut problem in graphs not contractible to K5.Oper. Res. Lett. 2 (1983) 107-111. MR 0717742, 10.1016/0167-6377(83)90016-0 |
| Reference:
|
[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. 10.1287/opre.36.3.493 |
| Reference:
|
[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. |
| Reference:
|
[F] M. Fiedler: Algebraic connectivity of graphs.Czechoslovak Math. J. 23 (98) (1973) 298-305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[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. MR 0740503, 10.1007/BF02591727 |
| Reference:
|
[GP] M. Grötschel, W. R. Pulleyblank: Weakly bipartite graphs and the max-cut problem.Oper. Res.Lett. / (1981) 23-27. MR 0643056, 10.1016/0167-6377(81)90020-1 |
| Reference:
|
[H] F. Hadlock: Finding a maximum cut of a planar graph in polynomial time.SIAM J. on Comp. 4 (1975) 221-225. Zbl 0321.05120, MR 0379290, 10.1137/0204019 |
| Reference:
|
[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 0378476 |
| Reference:
|
[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 0392633 |
| Reference:
|
[L] P. Lankaster: Theory of Matrices.Acad. Press, New York-London 1969. MR 0245579 |
| Reference:
|
[Lo] L. Lovász: On the Shannon capacity of a graph.IEEE Trans. Inform. Theory 25 (1979) 1-7. MR 0514926, 10.1109/TIT.1979.1055985 |
| Reference:
|
[LPS] A. Lubotzky R. Phillips, P. Sarnak: Ramanujan graphs.Combinatorica, 8 (1988) 261-277. MR 0963118, 10.1007/BF02126799 |
| Reference:
|
[Ml] B. Mohar: Isoperimetric numbers of graphs.J. Comb. Th. B, to appear. Zbl 0719.05042, MR 1026065 |
| Reference:
|
[M2] B. Mohar: The Laplacian spectrum of graphs.submitted. Zbl 0840.05059 |
| Reference:
|
[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. MR 0836264, 10.1016/0167-6377(86)90031-3 |
| Reference:
|
[OD] G. I. Orlova, Y. G. Dorfman: Finding the maximal cut in a graph.Engrg. Cybernetics 10 (1972) 502-506. MR 0329962 |
| Reference:
|
[PT] S. Poljak, Z. Tuza: Maximum bipartite subgraphs of Kneser graphs.Graphs and Combinatorics, 3 (1987) 191-199. Zbl 0674.05064, MR 0932133, 10.1007/BF01788540 |
| Reference:
|
[PT1] S. Poljak, D. Turzík: A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound.Discrete Math. 58 (1986) 99-104. MR 0820844, 10.1016/0012-365X(86)90192-5 |
| Reference:
|
[PT2] S. Poljak, D. Turzík: Maximum bipartite subgraphs of circulants.submitted. |
| Reference:
|
[T] R. M. Tanner: Explicit concentrators from generalized n-gons.SIAM J. Alg. Disc. Meth. 5 (1984) 287-293. Zbl 0554.05045, MR 0752035, 10.1137/0605030 |
| . |
