Next: About this document


Svatopluk Poljak

February 1994

  1. A note on stable sets and colouring of graphs, Comment. Math. Univ. Carolinae 15 (1974) 307-309. MR 50#4369; Zbl 284.05105

  2. (with M. Boguszak and J. Tuma) Note on homomorphism interpolation theorem, Comment. Math. Univ. Carolinae 17 (1976) 105-109. MR 53#12964; Zbl 335.05007

  3. (with D. Turz´k) On amalgamation of graphs and essential sets of generators, Comment. Math. Univ. Carolinae 19 (1979) 359-369. MR 80a:05171; Zbl 276.05053

  4. (with D. Turz´k) Some equivalent formulations of the intersection problem of finitelly generated classes of graphs, Acta Sci. Math. 41 (1979) 357-374. MR 81c:05035; Zbl 427.05049

  5. (with V. Rödl) Orthogonal partitions and covering of graphs, Czechoslovak Mathematical Journal 105 (1980) 475-485. MR 82j:05088; Zbl 456.05051

  6. (with D. Turz´k) Weak join of matroids, Proc. 8th Winter School on Abstract Analysis, Math. Institute Czech. Acad. Sci. 1980, pp.130-133.

  7. (with J. Nesetril) Geometric and algebraic aspects of combinatorial optimization (in Czech), SOFSEM 1980, pp.35-77.

  8. (with J. Nesetril and D. Turz´k) Amalgamation of matroids and its applications, J. Combinatorial Theory Ser.B 31 (1981) 9-22. MR 82k:05080; Zbl 473.05021

  9. (with V. Rödl) On the arc-chromatic number of a digraph, J. Combinatorial Theory Ser.B 31 (1981) 190-198. MR 82j:05059; Zbl 472.05024

  10. (with A. Pultr) On the dimension of trees, Discrete Mathematics 34 (1981) 165-171. MR 82m:05040; Zbl 476.05075

  11. (with V. Rödl) On set systems determined by intersections, Discrete Mathematics 34 (1981) 173-184. MR 82e:05105; Zbl 474.05060

  12. (with V. Rödl and D. Turz´k) Complexity of representing graphs by set systems, Discrete Applied Mathematics 3 (1981) 301-312. MR 83j:68054; Zbl 473.68064

  13. (with A. Pultr and V. Rödl) On the dimension of Kneser graphs, in: Algebraic Methods in Graph Theory, eds. L. Lovász and V. T. Sós, Colloq. Math. Soc. János Bolyai 25, North-Holland, Amsterdam 1981, pp. 631-646. Zb 476.05077

  14. (with D. Turz´k) A note of dimension of Czechoslovak Mathematical Journal 106 (1981) 484-487. Zb 476.05076

  15. (with A. Pultr) Representing graphs by means of strong and weak products, Comment. Math. Univ. Carolinae 22 (1981) 449-466. MR 83d:05085 Zb 476.05074

  16. (with D. Turz´k and P. Pudlák) Extension of k-subsets to - existence versus costructability, Comment. Math. Univ. Carolinae 23 (1982) 337-349. MR 83h:68045 Zb 495.68059

  17. (with D. Turz´k) A polynomial algorithm for constructing a large bipartite subgraph with an application to satisfiability problem, Canadian Mathematical J. 24 (1982) 519-524. MR 83j:05048; Zbl 487.68058

  18. (with D. Turz´k) A note on sticky matroids, Discrete Mathematics 42 (1982) 119-123. MR 84d:05059; Zbl 491.05020

  19. (with M. Sura) An algorithm for graceful labelling of trees, Ars Combinatoria 14 (1982) 57-66. MR 84d:05150; Zbl 504.05029

  20. (with A. Pultr and V. Rödl) On qualitatively independent partitions and related problems, Discrete Applied Mathematics 6 (1983) 193-205. MR 85d:05024; Zbl 515.05009

  21. (with V. Rödl) On classes of graphs determined by forbidden subgraphs, Czechoslovak Mathematical Journal 108 (1983) 27-33. MR 84d:05129; Zbl 528.05054

  22. (with M. Sura) On periodical behaviour in societies with symmetrical relations, Combinatorica 3 (1983) 119-121. MR 85a:90022; Zbl 561.90008

  23. (with M. Sura) On a construction of graceful trees, in: Graphs and Other Combinatorial Topics (M. Fiedler ed.), Proc. of the Third Czech.Symp. on Graph Theory (Prague 1982), Teubner Texte zur Math. 59, Leipzig 1983, pp. 220-222. Zbl 528.05021

  24. (with A. Pultr and V. Rödl) On a product dimension of bipartite graphs, Journal of Graph Theory 7 (1983) 475-486. MR 85i:05202; Zbl 531.05038

  25. (with D. Turz´k) On systems, periods and semipositive mappings, Comment. Math. Univ. Carolinae 25 (1984) 597-614. Zbl 576.05059

  26. (with D. Turz´k) Amalgamation over uniform matroids, Czechoslovak Mathematical Journal 109 (1984) 239-246. MR 85i:05075; Zbl 553.05029

  27. (with D. Turz´k) Amalgamation of matroids along hypergraphs, in: Finite and Infinite Sets ( eds. A. Hajnal, L. Lovász and V. T. Sós), Colloq. Math. Soc. Janos Bolyai 37, North-Holland, Amsterdam 1984, pp. 607-620. MR 87a:05048; Zbl 567.05015

  28. (with J. Nesetril and D. Turz´k) Some remarks on the Ramsey matroids, Supplemento ai Rendiconto del Circolo Matematico di Palermo, Serie II, n.3 (1984), Proceeding of the 11th Winter School on Abstract Analysis, pp. 185-189. Zbl 543.05021

  29. (with D. Turz´k) On social influence models with ranking alternatives and local election rules, Mathematical Social Sciences 10 (1985) 189-198.

  30. (with J. Pelant) Extensions of cyclically monotone mappings, Supplemento ai Rendiconto del Circolo Matematico di Palermo, Serie II, n.11 (1985), Proceeding of the 13th Winter School on Abstract Analysis, pp. 81-88. Zbl 586.90005

  31. (with J. Nesetril) On the complexity of the subgraph problem , Comment. Math. Univ. Carolinae 26 (1985) 415-419. Zbl 571.05050

  32. (with J. Nesetril and D. Turz´k) Special amalgams of matroids, in: Matroid Theory, eds. L. Lovász and A. Recski, Colloq. Math. Soc. János Bolyai 40, North-Holland, Amsterdam 1985, pp. 267-298. MR 87k:05053

  33. (with J. Nesetril) A note on max-cut problem with an application to discrete-analogue convertors, Operations Research Letters 4 (1986) 289-191. Zbl 585.90085

  34. (with D. Turz´k) On an application of convexity to discrete systems, Discrete Applied Mathematics 13 (1986) 27-32. MR 87k:58133; Zbl 588.93048

  35. (with D. Turz´k) On pre-periods of discrete influence systems, Discrete Applied Mathematics 13 (1986) 33-39. MR 87k:58134;

  36. (with D. Turz´k) A polynomial heuristic for certain subgraph optimization problems with guaranteed lower bound, Discrete Mathematics 58 (1986) 99-104. Zbl 585.05032

  37. (with J. Pelant and D. Turz´k) Limit behaviour of trajectories involving subgradients of convex functions, Comment. Math. Univ. Carolinae 28 (1987) 457-466.

  38. (with D. Turz´k) On a facet of the balanced subgraph polytope, Cas. pest. matem. 112 (1987) 373-380.

  39. (with M. Chrobak) A generalization of Smith's Theorem, Zastosowania Matematyki (Applic. Math.) XIX (1987) 371-374.

  40. (with Zs. Tuza) Maximum bipartite subgraphs of Kneser graphs, Graphs and Combinatorics 3 (1987) 191-199.

  41. Transformations on graphs and convexity, Complex Systems 1 (1987) 1021-1033.

  42. (with M. Loebl) Matroids induced by packing subgraphs, J. Combinatorial Theory Ser.B 44 (1988) 338-354.

  43. (with D. Turz´k) Subgradients of convex functions and periodical behaviour of finite automata, Proc. of Inst. Chem. Tech. (Prague), M 2 (1988), 75-86.

  44. (with M. Loebl) On the union of matching matroids, Mathematica Slovaca 38 (1988) 301-304.

  45. (with M. Loebl) Bipartite packing, in: Combinatorics, Eger (Hungary) 1987, Colloq. Math. Soc. János Bolyai 52, North-Holland, Amsterdam 1988, pp. 375-384.

  46. (with M. Chrobak) On common edges in optimal solutions to travelling salesman and and other optimization problems, Discrete Applied Mathematics 20 (1988) 101-111.

  47. (with V. Rödl and J. Spencer) Polynomial time algorithm for tournament ranking that ensures the expected profit, SIAM J. on Discrete Mathematics, 1 (1988) 372-376.

  48. (with Zs. Tuza) Improved bounds for the number of qualitetively independent partitions, J. Combinatorial Theory Ser.A 51 (1989) 111-116.

  49. Maximum rank of powers of a matrix of a given pattern, Proceedings AMS 106 (1989) 1137-1144.

  50. (with M. Loebl) A hierarchy of totally unimodular matrices, Discrete Mathematics 76 (1989) 241-246.

  51. (with P. Alles) Long induced paths and cycles in Kneser graphs, Graphs and Combinatorics 5 (1989) 303-306.

  52. On the generic dimension of controllable subspaces, IEEE Transactions on Automatic Control, March 1990, Vol.35, No.3, 367-369.

  53. (with M. Loebl) Subgraph packing - a survey. Topics in Combinatorics and Graph Theory: Essays in Honour of Gerhard Ringel, Physica-Verlag Heidelberg 1990, pp.491-503.

  54. (with K. Murota) Note on a graph-theoretic criterion for structural output controllability, IEEE Transactions on Automatic Control vol. 35, No 8 August 1990, 939-942.

  55. (with B.Mohar) Eigenvalues and the max-cut problem, Czechoslovak Mathematical Journal 40(115) (1990) 343-352.

  56. (with M. Kano) Graphs with the Balas-Uhry property, Journal of Graph Theory 14 (1990) 623-628.

  57. (with P. Alles and J. Nesetril) Extendabillity, dimensions and diagrams for cyclic orders, SIAM J. on Discrete Mathematics 4 (1991) 453-471.

  58. (with M. Schlegel) Computing generic Jordan canonical form, Linear and Multilinear Algebra 28 (1991) 241-249.

  59. (with T. Ibaraki) Weak three-linking in Eulerian digraphs, SIAM J. on Discrete Mathematics, 4 (1991) 84-98

  60. Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolinae 32,2 (1991) 209-212.

  61. Polyhedral and eigenvalue approximations of the max-cut problem. in: "Sets, Graphs and Numbers" (eds. G. Halász, L. Lovász, D. Miklós and T. Szönyi), Colloq. Math. Soc. János Bolyai 60, North-Holland, Amsterdam 1992, pp. 569-581.

  62. (with M. Loebl) Packing by families of subgraphs, in Forth Czechoslovakian Symposium on Combinatorics, Graph Theory and complexity, (M. Fiedler and J. Nesetril eds.), Annals of Discrete Mathematics 51, North-Holland 1992, pp. 181-186.

  63. (with Y. Crama and M. Loebl) On line balancing of strongly unimodular matrices, Discrete Applied Mathematics, 102 (1992) 143-147.

  64. (with M. Deza and M. Laurent) Facets of the cut cone III: The role of triangle facets, Graphs and Combinatorics 8 (1992) 125-142.

  65. (with M. Laurent) The metric polytope, Proc of IPCO 1992, (eds. E. Balas, G. Cornuejols and R. Kannan), 1992, pp. 274-286.

  66. Minimum spectral radius of a weighted graph, Linear Algebra and Its Applications, 171 (1992) 53-63.

  67. (with J. Kratochv´l) Compatible two-factors, Discrete Applied Mathematics, 36 (1992) 253-266.

  68. (with D. Turz´k) Maximum cut in circulant graphs, Discrete Mathematics, 108 (1992) 379-392.

  69. On the gap between structural controllability of time-invariant and time-varying systems, IEEE Transactions on Automatic Control, 37 (1992) 1961-1965.

  70. (with Ch. Delorme) The performance of an eigenvalue bound in some classes of graphs, in Proceedings of the Conference on Combinatorics, Marseille 1990. Discrete Mathematics, 111 (1993) 145-156.

  71. On existence theorems, in Proceedings of the Conference on Combinatorics, Marseille 1990. Discrete Mathematics, 122 (1993) 423-434.

  72. (with B. Mohar) Eigenvalue methods in combinatorial optimization, in: Combinatorial and Graph-Theoretic Problems in Linear Algebra, (eds. R. Brualdi, S. Friedland and V. Klee), The IMA Volumes in Mathematics and its Applications, vol. 50, Springer-Verlag 1993, pp. 107-151.

  73. (with J. Bang-Jensen) Eulerian trails through a set of terminals in specific, unique and all orders. In: "Graph Structure Theory", Proc. AMS-IMS-SIAM Joint Summer Conf. (Seattle 1991), eds. N. Robertson and P. Seymour, Contemporary Mathematics vol. 147, Amer. Mat. Soc. 1993, pp. 247-258.

  74. (with Ch. Delorme) Combinatorial properties and the complexity of an eigenvalue approximation of the max-cut problem, Europ. J. Combinatorics 14 (1993) 313-333.

  75. (with J. Rohn) Checking robust nonsingularity is NP-hard, Mathematics of Control, Signals and Systems 6 (1993) 1-9.

  76. (with Ch. Helmberg, B. Mohar, and F. Rendl) A spectral approach to bandwidth and separator problems in graphs, Third IPCO Conference (G. Rinaldi and L. Wolsey, eds.), 1993 pp. 183-194.

  77. (with M. Loebl) Efficient subgraph packing. J. Combinatorial Theory Ser.B, 59 (1993) 106-121.

  78. (with Ch. Delorme) Laplacian eigenvalues and the maximum cut problem, Mathematical Programming 63 (1993) 557-574.

  79. (with T.Nishizeki) K-connectivity and decomposition of graphs into forests, Discrete Applied Mathematics, 55 (1994) 295-301.

  80. (with Zs. Tuza) Bipartite subgraphs of triangle free graphs, SIAM J. Discrete Math. 7 (1994) 307-314.

  81. (with F. Rendl) Computational experiments with node and edge relaxations of the max-cut problem, Computing 52 (1994) 123-137.

  82. (with Zs. Tuza) On the expected relative error of the polyhedral approximation of the max-cut, Oper. Res. Letters 16 (1994) 191-198.

  83. (with F. Rendl) Computing the max-cut by eigenvalues, to appear in a special volume of Annals of Operation Research.

  84. (with F. Rendl) Nonlinear relaxation of the graph-bisection problems, to appear in SIAM J. Opt.

  85. (with Ch. Helmberg, B. Mohar, and F. Rendl) A spectral approach to bandwidth and separator problems in graphs, to appear in Linear and Multilinear Algebra.

  86. (with G. Hahn and P. Hell) On the ultimate independence ratio of a graph, Report No. 91717-OR (Institut für Diskrete Mathematik, Universität Bonn), Europ. J. Combinatorics 16 (1995). to appear.

  87. (with M. Laurent) One-third integrality in the metric polytope, Research Report (CWI Amsterdam) 1992, Mathematical Programming, to appear.

  88. Integer linear programs and local search, to appear in SIAM J. Comp.

  89. (with H. Wolkowicz) Convex relaxations of 0-1 quadratic programming, Mathematics of Operation Research, 20:550-561, 1995.

  90. (with M. Laurent) On a positive semidefinite relaxation of the cut polytope, Linear Algebra and Its Applications, 223/224:439-461, 1995.

  91. (with Zs. Tuza) Max-cut - a survey, preprint Academia Sinica, 1993.

  92. (with Zs. Tuza) Max-cut problem and large bipartite subgraphs, submitted to DIMACS Series (Special Year in Combinatorial Optimization, L. Lovasz, P. Seymour eds.)

  93. (with M. Laurent) On the facial structure of the correlation matrices, SIAM J. Matrix Analysis, 17:530--547, 1996.

  94. (with M. Laurent and F. Rendl) Connections between semidefinite relaxations of the max-cut and stable set problems, Mathematical Programming, to appear.

  95. (with F. Rendl and H. Wolkowicz) A recipe for semidefinite relaxation for (0,1)-quadratic programming, J. Global Optimization, 7:51-73, 1995.

  96. (with M. Laurent) On the gap inequalities Europ. J. Comb., 1996, to appear.

  97. (with D. Turzik) The probability of exact graphs, in preparation.

    F. Rendl and H. Wolkowicz) A semidefinite programming approach to integer programming, Proceedings of the 4th International IPCO Conference, Egon Balas and Jens Clausen (Eds.), Lecture Notes in Computer Science 920, Springer 1995, pp. 124-134.

  98. Neural Networks via Convexity and Linear Programming, submitted

  99. (with Ch. Delorme) Nonlinear relaxation of graph partition problems, in preparation.

  100. (with V.Rödl) Average discrepancy of a set system, in preparation.

  101. (with M. Laurent) Geometry of the metric polytope, in preparation.

  102. (with C. DeSimone, Ch. Helmberg, F. Rendl and G. Rinaldi) Polyhedral and semidefinite relaxations for the max-cut problem, in preparation.

Next: About this document

Fri Jan 5 09:26:03 EST 1996