Instytut Informatyki
Menu
badania

Publikacje

  • Publikacje Zakładu Złożoności Obliczeniowej i Analizy Algorytmów w roku 2019

    1. A. Abboud, L. Georgiadis, G. F. Italiano, R. Krauthgamer, N. Parotsidis, O. Trabelsi, P. Uznański, D. Wolleb-Graf, Faster algorithms for all-pairs bounded min-cuts, W: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) / Christel Baier, Ioanis Chatzigiannakis, Paola Flocchini, Stefano Leonardi (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 7:1-7:15. - (https://doi.org/10.4230/LIPIcs.ICALP.2019.7).
    2. P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn, P. Uznański, Improved analysis of deterministic load-balancing schemes, W: ACM Transactions on Algorithms. - Vol. 15, iss. 1 (2019), nr art. 10, s. 1-22. - (https://doi.org/10.1145/3282435).
    3. G. Bernardini, P. Gawrychowski, N. Pisanti, S. P. Pissis, G. Rosone, Even faster elastic-degenerate string matching via fast matrix multiplication, W: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) / Christel Baier, Ioanis Chatzigiannakis, Paola Flocchini, Stefano Leonardi (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 21:1-21:15. - (http://doi.org/10.4230/LIPIcs.ICALP.2019.21).
    4. P. Bille, P. Gawrychowski, I. L. Gørtz, G. M. Landau, O. Weimann, Top tree compression of tries, W: 30th International Symposium on Algorithms and Computation (ISAAC 2019) / Pinyan Lu, Guochuan Zhang (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 4:1-4:18. - (http://doi.org/10.4230/LIPIcs.ISAAC.2019.4).
    5. B. S. Chlebus, E. Hradovich, T. Jurdziński, M. Klonowski, D. R. Kowalski, Energy efficient adversarial routing in shared channels, W: The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019; Phoenix; United States; 22 June 2019-24 June 2019 / Christian Scheideler, Petra Berenbrink (eds.). - New York : ACM, 2019. - s. 191-200. - (https://doi.org/10.1145/3323165.3323190).
    6. S. Cicerone, G. D. Stefano, L. Gąsieniec, T. Jurdziński, A. Navarra, T. Radzik, G. Stachowiak, Fair hitting sequence problem: scheduling activities with varied frequency requirements, W: Algorithms and complexity ; 11th international conference, CIAC 2019, Rome, Italy, May 27-29, 2019 : proceedings / Pinar Heggernes (ed.). - Cham : Springer, 2019. - (LNCS ; vol. 11485). - s. 174-186. - (https://doi.org/10.1007/978-3-030-17402-6_15).
    7. R. Clifford, P. Gawrychowski, T. Kociumaka, D. P. Martin, P. Uznański, RLE edit distance in near optimal time, W: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) / Peter Rossmanith, Pinar Heggernes, Joost-Pieter Katoen (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum f~:ur Informatik, 2019. - s. 66:1-66:13. - (https://doi.org/10.4230/LIPIcs.MFCS.2019.66).
    8. B. Dudek, P. Gawrychowski, Computing quartet distance is equivalent to counting 4-cycles, W: STOC'19 : Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing : June 23-26, 2019,Phoenix, AZ, USA / Moses Charikar, Edith Cohen (eds.). - New York : Association for Computing Machinery (ACM), 2019. - s. 733-743. - (https://doi.org/10.1145/3313276.3316390).
    9. R. Ferens, M. Szykuła, Complexity of bifix-free regular languages, W: Theoretical Computer Science. - Vol. 787 (2019), s. 14-27. - (https://doi.org/10.1016/j.tcs.2018.09.016).
    10. G. Fici, P. Gawrychowski, Minimal absent words in rooted and unrooted trees, W: String Processing and Information Retrieval : 26th International Symposium, SPIRE 2019, Segovia, Spain, October 7-9, 2019, Proceedings / Nieves R. Brisaboa, Simon J Puglisi (eds.). - Cham : Springer, 2019. - (Lecture Notes in Computer Science ; vol. 11811). - s. 152-161.
    11. M. Ganardi, A. Jeż, M. Lohrey, Balancing string straight-line programs, W: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science 9-12 November 2019 Baltimore, Maryland / ed. Lisa O'Conner. - Piscataway : IEEE Computer Society, 2019. - s. 1169-1183. - (https://doi.org/10.1109/FOCS.2019.00073).
    12. M. Gańczorz, Entropy lower bounds for dictionary compression, W: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) / Nadia Pisanti, Solon P. Pissis (Hrsg.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 11:1-11:18. - (http://doi.org/10.4230/LIPIcs.CPM.2019.11).
    13. P. Garncarek, T. Jurdziński, D. R. Kowalski, M. A Mosteiro, mmWave wireless backhaul scheduling of stochastic packet arrivals, W: 2019 IEEE 33rd International Parallel and Distributed Processing Symposium / edited by Vinod Rebello. - Los Alamitos : IEEE Computer Society, 2019. - s. 708-717. - (https://doi.org/10.1109/IPDPS.2019.00079).
    14. Paweł Garncarek, Tomasz Jurdziński, Dariusz R. Kowalski, Stable memoryless queuing under contention, W: 33rd International Symposium on Distributed Computing (DISC 2019) / ed. Jukka Suomela. - [Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik], 2019. - s. 17:1-17:16. - (https://doi.org/10.4230/LIPIcs.DISC.2019.17).
    15. P. Garncarek, T. Jurdziński, D. R. Kowalski, K. Loryś, Online packet scheduling under adversarial errors, W: Theoretical Computer Science. - Vol. 795 (2019), s. 492-509. - (https://doi.org/10.1016/j.tcs.2019.08.003).
    16. P. Gawrychowski, Almost optimal distance oracles for planar graphs, W: STOC'19 : Proceedings of the 51th Annual ACM SIGACT Symposium on Theory of Computing : June 23-26, 2019,Phoenix, AZ, USA / Moses Charikar, Edith Cohen (eds.). - New York : Association for Computing Machinery (ACM), 2019. - s. 138-151. - (https://doi.org/10.1145/3313276.3316316).
    17. P. Gawrychowski, F. Manea, R. Mercas, D. Nowotka, Hide and seek with repetitions, W: Journal of Computer and System Sciences. - Vol. 101 (2019), s. 42-67. - (https://doi.org/10.1016/j.jcss.2018.10.004).
    18. P. Gawrychowski, F. Manea, R. Serafin, Fast and longest rollercoasters, W: 36th International Symposium on Theoretical Aspects of Computer Science : STACS 2019, March 13-16, 2019, Berlin, Germany / Rolf Niedermeier, Christophe Paul (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 30:1-30:17. - (https://doi.org/10.4230/LIPIcs.STACS.2019.30).
    19. P. Gawrychowski, O. Merkurev, A. M. Shur, P. Uznański, Tight tradeoffs for real-time approximation of longest palindromes in streams, W: Algorithmica. - Vol. 81, iss. 9 (2019), s. 3630-3654. - (https://doi.org/10.1007/s00453-019-00591-8).
    20. P. Gawrychowski, J. Radoszewski, T. Starikovskaya, Quasi-periodicity in streams, W: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) / Nadia Pisanti, Solon P. Pissis (Hrsg.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 22:1-22:14. - (http://doi.org/10.4230/LIPIcs.CPM.2019.22).
    21. P. Gawrychowski, T. Starikovskaya, Streaming dictionary matching with mismatches, W: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) / Nadia Pisanti, Solon P. Pissis (Hrsg.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 21:1-21:15. - (http://doi.org/10.4230/LIPIcs.CPM.2019.21).
    22. L. Gąsieniec, T. Jurdziński, R. Martin, G. Stachowiak, Communication and location discovery in geometric ring networks, W: Information and Computation. - Vol. 266 (2019), s. 19-48. - (https://doi.org/10.1016/j.ic.2018.12.001).
    23. L. Gąsieniec, G. Stachowiak, P. Uznański, Almost logarithmic-time space optimal leader election in population protocols, W: The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019; Phoenix; United States; 22 June 2019-24 June 2019 / Christian Scheideler, Petra Berenbrink (eds.). - New York : ACM, 2019. - s. 93-102.
    24. A. Jeż, Deciding context unification, W: Journal of the ACM. - Vol. 66, iss. 6 (2019), s. 39:1-39:45. - (https://doi.org/10.1145/3356904).
    25. A. Jeż, Deciding context unification (with regular constraints), W: 23rd international conference, DLT 2019, Warsaw, Poland, August 5-9, 2019, proceedings / Piotrek Hofman, Michał Skrzypczak (eds.). - Cham : Springer, 2019. - (Lecture Notes in Computer Science ; vol. 11647). - s. 18-40.
    26. Michał Karpiński, Marek Piotrów, Competitive sorter-based encoding of PB-constraints into SAT, W: Proceedings of Pragmatics of SAT 2015 and 2018 / Daniel Le Berre, Matti Järvisalo (eds.). - Manchester : EasyChair Publications, 2019. - s. 65-78. - (http://dx.doi.org/10.29007/hh3v).
    27. Michał Karpiński, Marek Piotrów, Encoding cardinality constraints using multiway merge selection networks, W: Constraints. - Vol. 24, iss. 3-4 (2019), s. 234-251. - (https://doi.org/10.1007/s10601-019-09302-0).
    28. A. Kosowski, P. Uznański, L. Viennot, Hardness of exact distance queries in sparse graphs through hub labeling, W: PODC '19 : proceedings of the 2019 ACM Symposium on Principles of Distributed Computing : July 29 - August 2, 2019, Toronto, ON, Canada / Peter Robinson, Faith Ellen (eds.). - New York : ACM, 2019. - s. 272-279
    29. J. Kowalski, M. Mika, J. Sutowicz, M. Szykuła, Regular boardgames, W: The Thirty-Third AAAI Conference on Artificial Intelligence, the Thirty-First Innovative Applications of Artificial Intelligence Conference, the Ninth AAAI Symposium on Educational Advances in Artificial Intelligence : Honolulu, Hawaii USA - January 27-February 1, 2019. - Palo Alto : AAAI Press, 2019. - s. 1699-1706. - (https://doi.org/10.1609/aaai.v33i01.33011699).
    30. K. Labib, P. Uznański, D. Wolleb-Graf, Hamming distance completeness, W: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) / Nadia Pisanti, Solon P. Pissis (Hrsg.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 14:1-14:17. - (https://doi.org/10.4230/LIPIcs.CPM.2019.14).
    31. G. D. Marco, T. Jurdziński, D. R. Kowalski, Optimal channel utilization with limited feedback, W: Fundamentals of Computation Theory : 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings / edited by Leszek Gąsieniec, Jesper Jansson, Christos Levcopoulos. - Cham : Springer, 2019. - (Lecture Notes in Computer Science ; vol. 11651). - s. 140-152. - (https://doi.org/10.1007/978-3-030-25027-0_10).
    32. G. D. Marco, D. R. Kowalski, G. Stachowiak, Deterministic contention resolution on a shared channel, W: 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019; Richardson, Texas, United States 7-9 July 2019. - Ding-Zhu Du (ed.). - Los Alamitos : IEEE Computer Society, 2019. - s. 472-482. - (https://doi.org/10.1109/icdcs.2019.00054).
    33. A. Schickedanz, D. Ajwani, U. Meyer, P. Gawrychowski, Average-case behavior of k-Shortest path algorithms, W: Complex Networks and Their Applications VII : Volume 1 Proceedings The 7th International Conference on Complex Networks and Their Applications - COMPLEX NETWORKS 2018 / Luca Maria Aiello, Chantal Cherifi, Hocine Cherifi, Renaud Lambiotte, Luis M. Rocha (eds.). - Cham : Springer, 2019. - (Studies in Computational Intelligence ; vol. 812). - s. 28-40. - (https://doi.org/10.1007/978-3-030-05411-3_3).
    34. J. Studený, P. Uznański, Approximating approximate pattern matching, W: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) / Nadia Pisanti, Solon P. Pissis (Hrsg.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. - s. 15:1-15:13. - (https://doi.org/10.4230/LIPIcs.CPM.2019.15).
    35. M. Szykuła, J. Wittnebel, Syntactic complexity of bifix-free regular languages, W: Theoretical Computer Science. - Vol. 787 (2019), s. 45-76. - (https://doi.org/10.1016/j.tcs.2018.12.025).

  • Publikacje Zakładu Złożoności Obliczeniowej i Analizy Algorytmów w roku 2018

    1. M. Berlinkov, R. Ferens, M. Szykuła, Complexity of preimage problems for deterministic finite automata, W: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) / Igor Potapov, Paul Spirakis, James Worrell (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs - Leibniz International Proceedings in Informatics ; 117).- S. 32:1-32:14 (https://doi.org/10.4230/LIPIcs.MFCS.2018.32).
    2. M. Bieńkowski, T. Jurdziński, M. Korzeniowski, D. Kowalski, Distributed online and stochastic queueing on a multiple access channel, W: ACM Transactions on Algorithms. - Vol. 14, nr 2 (2018), s. 21:1-21:22 (https://doi.org/10.1145/3182396).
    3. J. Brzozowski, L. Kari, B. Li, M. Szykuła, State complexity of overlap assembly, W: Implementation and Application of Automata : 23rd International Conference, CIAA 2018, Charlottetown, PE, Canada, July 30 - August 2, 2018, Proceedings / Cezar Câmpeanu (ed.). - Cham : Springer International Publishing - Springer, 2018. - (Lecture Notes in Computer Science ; 10977).- S. 109-120 (https://doi.org/10.1007/978-3-319-94812-6_10).
    4. J. Brzozowski, M. Szykuła, Syntactic complexity of suffix-free languages, W: Information and Computation. - Vol. 259, Part 2 (2018), s. 174-190 (https://doi.org/10.1016/j.ic.2017.08.014).
    5. J. Brzozowski, M. Szykuła, Y. Ye, Syntactic complexity of regular ideals, W: Theory of Computing Systems. - Vol. 62, iss. 5 (2018), s. 1175-1202 (https://doi.org/10.1007/s00224-017-9803-8).
    6. H. Chang, P. Gawrychowski, S. Mozes, O. Weimann, Near-optimal distance emulator for planar graphs, W: 26th Annual European Symposium on Algorithms (ESA 2018) / Editors Yossi Azar, Hannah Bast, Grzegorz Herman. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs : 112). - S. 16:1-16:17 (https://doi.org/10.4230/LIPIcs.ESA.2018.16).
    7. H. Chuangpishit, J. Czyzowicz, L. Gąsieniec, K. Georgiou, T. Jurdziński, E. Kranakis, Patrolling a path connecting a set of points with unbalanced frequencies of visits, W: SOFSEM 2018: Theory and Practice of Computer Science : 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29 - February 2, 2018, Proceedings / A Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiří Wiedermann (eds.). - Cham : Springer International Publishing - Edizioni della Normale, 2018. - (Lecture Notes in Computer Science ; 10706). - S. 367-380. - Bibliogr. - Streszcz. w jęz. ang. (https://doi.org/10.1007/978-3-319-73117-9_26).
    8. B. Dudek, P. Gawrychowski, Edit distance between unrooted trees in cubic time, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T. Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 45:1-45:14 (https://doi.org/10.4230/LIPIcs.ICALP.2018.45).
    9. B. Dudek, P. Gawrychowski, Slowing down top trees for better worst-case compression, W: 29th Annual Symposium on Combinatorial Pattern Matching : CPM 2018, July 2-4, 2018, Qingdao, China / Editors Gonzalo Navarro, David Sankoff, Binhai Zhu. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 105). - S. 16:1-16:8 (https://doi.org/10.4230/LIPIcs.CPM.2018.16).
    10. B. Dudek, A. Kosowski, Universal protocols for information dissemination using emergent signals, W: STOC'18 : Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing : June 25-29, 2018, Los Angeles, CA, USA / Editors Ilias Diakonikolas, David Kempe, Monika Henzinger. - New York : ACM, 2018. - S. 87-99 (https://doi.org/10.1145/3188745.3188818).
    11. M. Ganardi, A. Jeż, M. Lohrey, Sliding windows over context-free languages, W: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) / editors: Igor Potapov, Paul Spirakis, James Worrell. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 117). - S. 15:1-15:15 (https://doi.org/10.4230/LIPIcs.MFCS.2018.15).
    12. P. Garncarek, T. Jurdziński, D. Kowalski, Local queuing under contention, W: 32nd International Symposium on Distributed Computing (DISC 2018) / editors Ulrich Schmid, Josef Widder. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPICS ; 121). - S. 28:1-28:18 (https://doi.org/10.4230/LIPIcs.DISC.2018.28).
    13. P. Gawrychowski, A. Karczmarz, Improved bounds for shortest paths in dense distance graphs, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T. Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 61:1-61:15 (https://doi.org/10.4230/LIPIcs.ICALP.2018.61).
    14. P. Gawrychowski, A. Karczmarz, T. Kociumaka, J. Łącki, P. Sankowski, Optimal dynamic strings, W: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 / Artur Czumaj (ed.). - Philadelphia : Society for Industrial and Applied Mathematics, 2018. - (Proceedings).- S. 1509-1528 (https://doi.org/10.1137/1.9781611975031.99).
    15. P. Gawrychowski, F. Kuhn, J. Łopuszański, K. Panagiotou, P. Su, Labeling schemes for nearest common ancestors through minor-universal trees, W: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 / Artur Czumaj (ed.). - Philadelphia : Society for Industrial and Applied Mathematics, 2018. - (Proceedings).- S. 2604-2619 (https://doi.org/10.1137/1.9781611975031.166).
    16. P. Gawrychowski, G. Landau, T. Starikovskaya, Fast entropy-bounded string dictionary look-up with mismatches, W: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) / Editors Igor Potapov, Paul Spirakis, James Worrell. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs : 117). - S. 66:1-66:15 (https://doi.org/10.4230/LIPIcs.MFCS.2018.66).
    17. P. Gawrychowski, G. Landau, W. Sung, O. Weimann, A faster construction of greedy consensus trees, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 63:1-63:14 (https://doi.org/10.4230/LIPIcs.ICALP.2018.63).
    18. P. Gawrychowski, L. Markin, O. Weimann, A faster FPTAS for #knapsack, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T. Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 64:1-64:13 (https://doi.org/10.4230/LIPIcs.ICALP.2018.64).
    19. P. Gawrychowski, P. Uznański, Towards unified approximate pattern matching for hamming and L1 Distance, W: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) / Editors Ioanis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald T. Sannella. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 107). - S. 62:1-62:13 (https://doi.org/10.4230/LIPIcs.ICALP.2018.62).
    20. M. Gańczorz, P. Gawrychowski, A. Jeż, T. Kociumaka, Edit distance with block operations, W: 26th Annual European Symposium on Algorithms (ESA 2018) / Editors Yossi Azar, Hannah Bast, Grzegorz Herman. - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs ; 112). - S. 33:1-33:14 (https://doi.org/10.4230/LIPIcs.ESA.2018.33).
    21. M. Ghaffari, K. Nowicki, Congested clique algorithms for the minimum cut problem, W: PODC'18 : proceedings of the 2018 ACM Symposium on Principles of Distributed Computing : July 23-27, 2018, Egham, United Kingdom / Editors Calvin Newport, Idit Keidar. - New York : ACM, 2018. - S. 357-366 (https://doi.org/10.1145/3212734.3212750).
    22. L. Gąsieniec, G. Stachowiak, Fast space optimal leader election in population protocols, W: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 / Artur Czumaj (ed.). - Philadelphia : Society for Industrial and Applied Mathematics, 2018. - (Proceedings).- S. 2653-2667 (https://doi.org/10.1137/1.9781611975031.169).
    23. A. Jeż, A. Okhotin, On the number of nonterminal symbols in unambiguous conjunctive grammars, W: Fundamenta Informaticae. - Vol. 162, nr 1 (2018), s. 43-72 (https://doi.org/10.3233/FI-2018-1713).
    24. T. Jurdziński, D. Kowalski, M. Różański, G. Stachowiak, Deterministic digital clustering of wireless Ad Hoc networks, W: PODC'18 : proceedings of the 2018 ACM Symposium on Principles of Distributed Computing : July 23-27, 2018, Egham, United Kingdom / Editors Calvin Newport, Idit Keidar. - New York : ACM, 2018. - S. 105-114 (https://doi.org/10.1145/3212734.3212752).
    25. T. Jurdziński, K. Loryś, K. Nowicki, Communication complexity in vertex partition whiteboard model, W: Structural Information and Communication Complexity : 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers / Editors Zvi Lotker, Boaz Patt-Shamir. - Cham : Springer, 2018. - S. 264-279 (https://doi.org/10.1007/978-3-030-01325-7_24).
    26. T. Jurdziński, K. Nowicki, MST in O(1) rounds of congested clique, W: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018 / Artur Czumaj (ed.). - Philadelphia : Society for Industrial and Applied Mathematics, 2018. - (Proceedings). - S. 2620-2632. - Bibliogr. - Streszcz. w jęz. ang. (https://doi.org/10.1137/1.9781611975031.167).
    27. T. Jurdziński, K. Nowicki, On range and edge capacity in the congested clique, W: SOFSEM 2018: Theory and Practice of Computer Science : 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29 - February 2, 2018, Proceedings / A. Min Tjoa, Ladjel Bellatreche, Stefan Biffl, Jan van Leeuwen, Jiří Wiedermann (eds.). - Cham : Springer International Publishing - Edizioni della Normale, 2018. - (Lecture Notes in Computer Science ; 10706). - S. 305-318. - Bibliogr. - Streszcz. w jęz. ang. (https://doi.org/10.1007/978-3-319-73117-9_22).
    28. T. Jurdziński, K. Nowicki, Connectivity and minimum cut approximation in the broadcast congested clique, W: Structural Information and Communication Complexity : 25th International Colloquium, SIROCCO 2018, Ma'ale HaHamisha, Israel, June 18-21, 2018, Revised Selected Papers / Editors Zvi Lotker, Boaz Patt-Shamir. - Cham : Springer, 2018. - S. 331-344 (https://doi.org/10.1007/978-3-030-01325-7_28).
    29. M. Karpiński, Encoding cardinality constraints using standard encoding of generalized selection networks preserves arc-consistency, W: Theoretical Computer Science. - Vol. 707 (2018), s. 77-81 (https://doi.org/10.1016/j.tcs.2017.09.036).
    30. M. Karpiński, K. Piecuch, On vertex coloring without monochromatic triangles, W: Computer Science - Theory and Applications : 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018 : Proceedings / Fedor V. Fomin, Vladimir V. Podolskii (eds.). - Cham : Springer International Publishing , 2018. - (Lecture Notes in Computer Science ; 10846). - S. 220-231. - Bibliogr. - Streszcz. w jęz. ang. (https://doi.org/10.1007/978-3-319-90530-3_19).
    31. J. Kowalski, A. Kisielewicz, Regular language inference for learning rules of simplified boardgames, W: CIG 2018 : proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG'18) : Department of Data Science and Knowledge Engineering, Maastricht University, Maastricht, The Netherlands, 14-17 August, 2018 / editor Mark H.M. Winands. - Piscataway : IEEE, 2018. - S. 78-85 (https://doi.org/10.1109/CIG.2018.8490435).
    32. J. Kowalski, A. Liapis, Ł. Żarczyński, Mapping chess aesthetics onto procedurally generated chess-like games, W: Applications of Evolutionary Computation : 21st International Conference, EvoApplications 2018, Parma, Italy, April 4-6, 2018, Proceedings / Kevin Sim, Paul Kaufmann (eds.). - Cham : Springer, 2018. - (Lecture Notes in Computer Science ; 10784).- S. 325-341 (https://doi.org/10.1007/978-3-319-77538-8_23).
    33. I. Podolak, A. Roman, M. Szykuła, B. Zieliński, A machine learning approach to synchronization of automata, W: Expert Systems with Applications. - Vol. 97 (2018), s. 357-371 (https://doi.org/10.1016/j.eswa.2017.12.043).
    34. A. Ryzhikov, M. Szykuła, Finding short synchronizing words for prefix codes, W: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) / Igor Potapov, Paul Spirakis, James Worrell (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs - Leibniz International Proceedings in Informatics ; 117).- S. 21:1-21:14 (https://doi.org/10.4230/LIPIcs.MFCS.2018.21).
    35. M. Szykuła, Improving the upper bound on the length of the shortest reset words, W: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) / Rolf Niedermeier, Brigitte Vallée (Eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. - (LIPIcs - Leibniz International Proceedings in Informatics ; 96).- S. 56:1-56:13 (https://doi.org/10.4230/LIPIcs.STACS.2018.56).

  • Publikacje Zakładu Złożoności Obliczeniowej i Analizy Algorytmów w roku 2017

    1. M. Karpiński, Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete, Theoretical Computer Science. - Vol. 659 (2017), s. 88-94. (http://dx.doi.org/10.1016/j.tcs.2016.10.011)
    2. M. Ganardi, D. Hucke, A. Jeż, M. Lohrey, E. Noeth, Constructing small tree grammars and small circuits for formulas, Journal of Computer and System Sciences. - Vol. 86 (2017), s. 136-158. (https://doi.org/10.1016/j.jcss.2016.12.007)
    3. M. Gańczorz, A. Jeż, Improvements on Re-Pair grammar compressor, // W: DCC 2017 : 2017 Data Compression Conference : 4-7 April 2017, Snowbird, Utah, USA : proceedings / Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagrista, James A. Storer (eds.). - Piscataway : IEEE, 2017. - (Proceedings). - S. 181-190. (http://dx.doi.org/10.1109/DCC.2017.52)
    4. A. Jeż, Recompression: new approach to word equations and context unification (Invited Talk), // W: 34th Symposium on Theoretical Aspects of Computer Science : STACS 2017, March 8-11, 2017, Hannover, Germany / Heribert Vollmer, Brigitte Vallée (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - ( LIPIcs - Leibniz International Proceedings in Informatics ; 66). - S. 2-1-2-3. (http://dx.doi.org/10.4230/LIPIcs.STACS.2017.2)
    5. A. Jeż, A. Okhotin, Unambiguous conjunctive grammars over a one-symbol alphabet, Theoretical Computer Science. - Vol. 665 (2017), s. 13-39. (https://doi.org/10.1016/j.tcs.2016.12.009)
    6. A. Jeż, Word equations in nondeterministic linear space // W: 44th International Colloquium on Automata, Languages, and Programming : ICALP 2017, Warsaw, Poland, July 10-14, 2017 / Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, Anca Muscholl (eds.). - Saarbrücken/Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 80). - S. 95-1-95-13. (http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.95)
    7. J. Kowalski, A. Roman, A new evolutionary algorithm for synchronization, // W: Applications of Evolutionary Computation : 20th European Conference, EvoApplications 2017, Amsterdam, The Netherlands, April 19-21, 2017, Proceedings, Part I / Giovanni Squillero, Kevin Sim (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10199).- S. 620-635. (http://dx.doi.org/10.1007/978-3-319-55849-3_40)
    8. L. Gąsieniec, D. Hamilton, R. Martin, P.G. Spirakis, G. Stachowiak, Deterministic population protocols for exact majority and plurality, // W: 20th International Conference On Principles Of Distributed Systems (OPODIS-16), December 13-16th, 2016, Madrid, Spain / Panagiota Fatourou, Ernesto Jiménez, Fernando Pedone (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (LIPIcs - Leibniz Internation Proceedings in Informatics ; 70).- S. 14-1-14-14. (http://dx.doi.org/10.4230/LIPIcs.OPODIS.2016.14)
    9. V.V. Gusev, E. Pribavkina, M. Szykuła, Around the road coloring theorem, // W: Proceedings of the Fourth Russian-Finnish Symposium on Discrete Mathematics Organized in Turku on 16.-19.5.2017 / Juhani Karhumäki, Yuri Matiyasevich, Aleksi Saarela (eds.). - Turku : Turku Centre for Computer Science, 2017. - (TUCS Lecture Notes ; 26). - S. 52-56.
    10. R. Ferens, M. Szykuła, Complexity of bifix-free regular languages, // W: Implementation and Application of Automata : 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings / Arnaud Carayol, Cyril Nicaud (eds.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10329). - S. 76-88. (http://dx.doi.org/10.1007/978-3-319-60134-2_7)
    11. J.A. Brzozowski, M. Szykuła, Complexity of suffix-free regular languages, Journal of Computer and System Sciences. - Vol. 89 (2017), s. 270-287. (http://dx.doi.org/10.1016/j.jcss.2017.05.011)
    12. M. Szykuła, J. Wittnebel, Syntactic complexity of bifix-free languages, // W: Implementation and Application of Automata : 22nd International Conference, CIAA 2017, Marne-la-Vallée, France, June 27-30, 2017, Proceedings / Arnaud Carayol, Cyril Nicaud (eds.). - Cham : Springer, 2017. - (Lecture Notes in Computer Science ; 10329). - S. 201-212. (http://dx.doi.org/10.1007/978-3-319-60134-2_17)
    13. T. Jurdziński, M. Różański, Deterministic oblivious local broadcast in the SINR model, // W: Fundamentals of Computation Theory : 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings / Ralf Klasing, Marc Zeitoun (eds.). - Berlin, Heidelberg : Springer, 2017. - (Lecture Notes in Computer Science ; 10472). - S. 312-325. (https://doi.org/10.1007/978-3-662-55751-8_25)
    14. P. Garncarek, T. Jurdziński, K. Loryś, Fault-tolerant online packet scheduling on parallel channels, // W: 2017 IEEE 31st International Parallel and Distributed Processing Symposium : IPDPS 2017 : proceedings : 29 May-2 June 2017, Orlando, Florida / Michela Taufer (general chair). - Piscataway, NJ : IEEE, 2017. - S. 347-356. (https://doi.org/10.1109/IPDPS.2017.105)
    15. B.S. Chlebus, V. Cholvi, P. Garncarek, T. Jurdziński, D.R. Kowalski, Routing in wireless networks with interferences, IEEE Communications Letters. - Vol. 21, iss. 9 (2017), s. 2105 - 2108. (https://doi.org/10.1109/LCOMM.2017.2716348)
    16. G. De Marco, T. Jurdziński, M. Różański, G. Stachowiak, Subquadratic non-adaptive threshold group testing, // W: Fundamentals of Computation Theory : 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings / Ralf Klasing, Marc Zeitoun (eds.). - Berlin, Heidelberg : Springer, 2017. - (Lecture Notes in Computer Science ; 10472). - S. 177-189. (https://doi.org/10.1007/978-3-662-55751-8_15)
    17. D. Alistarh, B. Dudek, A. Kosowski, D. Soloveichik, P. Uznański, Robust detection in leak-prone population protocols, // W: DNA Computing and Molecular Programming : 23rd International Conference, DNA 23, Austin, TX, USA, September 24-28, 2017, Proceedings / Robert Brijder, Lulu Qian (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10467). - S. 155-171. (https://doi.org/10.1007/978-3-319-66799-7_11)
    18. M. Abdulazeez, P. Garncarek, P.W.H. Wong, Lightweight framework for reliable job scheduling in heterogeneous clouds, // W: ICCCN 2017 : 2017 26th International Conference on Computer Communications and Networks (ICCCN) : July 31-August 3, 2017, Vancouver, Canada / Christian Poellabauer (general chair). - Piscataway : IEEE, 2017. - S. 1-6. (https://doi.org/10.1109/ICCCN.2017.8038506)
    19. M. Abdulazeez, P. Garncarek, D.R. Kowalski, P.W.H. Wong, Lightweight robust framework for workload scheduling in clouds, // W: 2017 IEEE 1st International Conference on Edge Computing - IEEE EDGE 2017 : 25-30 June 2017, Honolulu, Hawaii, USA : proceedings / Andrzej M. Goscinski, Min Luo (eds.). - Piscataway : IEEE, 2017. - S. 206-209. (https://doi.org/10.1109/IEEE.EDGE.2017.36)
    20. B. Dudek, P. Gawrychowski, P. Ostropolski-Nalewaja, A family of approximation algorithms for the maximum duo-preservation string mapping problem // W: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) / Juha Kärkkäinen, Jakub Radoszewski, Wojciech Rytter (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (LIPIcs - Leibniz International Proceedings in Informatics ; 78).- S. 10-1-10-14. (https://doi.org/10.4230/LIPIcs.CPM.2017.10)
    21. A. Fernández Anta, T. Jurdziński, M.A. Mosteiro, Y. Zhang, Algorithms for Sensor Systems : 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers / Cham : Springer International Publishing, 2017. - X, 237 s.(https://doi.org/10.1007/978-3-319-72751-6)
    22. T. Jurdziński, K. Nowicki, Brief announcement: on connectivity in the broadcast congested clique, // W: 31st International Symposium on Distributed Computing (DISC 2017) / Andréa W. Richa (Ed.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (LIPIcs - Leibniz International Proceedings in Informatics ; 91). - S. 54:1-54:4. (https://doi.org/10.4230/LIPIcs.DISC.2017.54)
    23. T. Jurdziński, M. Różański, G. Stachowiak, Token traversal in ad hoc wireless networks via implicit carrier sensing, // W: Structural Information and Communication Complexity : 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017 / Shantanu Das, Sebastien Tixeuil (eds.). - Cham : Springer International Publishing - Springer, 2017. - (Lecture Notes in Computer Science ; 10641). - S. 15-33. (https://doi.org/10.1007/978-3-319-72050-0_2)
    24. J. Kowalski, Ł. Żarczyński, A. Kisielewicz, Evaluating chess-like games using generated natural language descriptions, // W: Advances in Computer Games : 15th International Conferences, ACG 2017, Leiden, The Netherlands, July 3-5, 2017, Revised Selected Papers / Mark H.M. Winands, H. Jaap van den Herik, Walter A. Kosters (eds.). - Cham : Springer International Publishing, 2017. - (Lecture notes in computer science ; 10664).- S. 127-139. (https://doi.org/10.1007/978-3-319-71649-7_11)
    25. B. Kostka, J. Kwiecieli, J. Kowalski, P. Rychlikowski, Text-based adventures of the golovin AI agent, // W: 2017 IEEE Conference on Computational Intelligence and Games (CIG) : New York, NY, USA, August 22th-August 25th, 2017 / Samad Ahmadi (ed.). - Piscataway : IEEE, 2017.- S. 181-188. (https://doi.org/10.1109/CIG.2017.8080433)
    26. G. De Marco, G. Stachowiak, Asynchronous shared channel, // W: Proceedings of the ACM Symposium on Principles of Distributed Computing - PODC'17 / Elad Michael Schiller (general chair). - New York : ACM, 2017. - S. 391-400. (https://doi.org/10.1145/3087801.3087831)
    27. M. Dżyga, R. Ferens, V.V. Gusev, M. Szykuła, Attainable values of reset thresholds, // W: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) / Kim G. Larsen, Hans L. Bodlaender, Jean-Francois Raskin (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. - (LIPIcs - Leibniz International Proceedings in Informatics ; 83).- S. 40-1-40-14. ( https://doi.org/10.4230/LIPIcs.MFCS.2017.40)

  • Publikacje Zakładu Złożoności Obliczeniowej i Analizy Algorytmów w roku 2016

    1. A. Jeż, One-variable word equations in linear time, Algorithmica. - Vol. 74, iss. 1 (2016), s. 1-48. (http://dx.doi.org/10.1007/s00453-014-9931-3)
    2. A. Jeż, A really simple approximation of smallest grammar, Theoretical Computer Science. - Vol. 616 (2016), s. 141-150. (http://dx.doi.org/10.1016/j.tcs.2015.12.032)
    3. A. Jeż, A. Okhotin, Equations over sets of integers with addition only, Journal of Computer and System Sciences. - Vol. 82, Iss. 6 (2016), s. 1007-1019. (http://dx.doi.org/10.1016/j.jcss.2016.02.003)
    4. A. Jeż, A. Okhotin, Least and greatest solutions of equations over sets of integers, Theoretical Computer Science. - Vol. 619 (2016), s. 68-86. (http://dx.doi.org/10.1016/j.tcs.2016.01.013)
    5. A. Jeż, Recompression: a simple and powerful technique for word equations, Journal of the ACM. - Vol. 63, iss. 1 (2016), nr art. 4. (http://dx.doi.org/10.1145/2743014)
    6. V. Diekert, A. Jeż, M. Kufleitner, Solutions of word equations over partially commutative structures, W: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) / Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi (eds.). - Wadern : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. - (Leibniz International Proceedings in Informatics (LIPIcs) ; 55). - S. 127:1-127:14. (http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.127)
    7. A. Kisielewicz, J. Kowalski, M. Szykuła, Experiments with synchronizing automata, W: Implementation and Application of Automata : 21st International Conference, CIAA 2016, Seoul, South Korea, July 19-22, 2016, Proceedings / Yo-Sub Han, Kai Salomaa (eds.). - Cham : Springer International Publishing - Springer, 2016. - (Lecture Notes in Computer Science ; 9705).- S. 176-188. (http://dx.doi.org/10.1007/978-3-319-40946-7_15)
    8. J. Kowalski, A. Kisielewicz, Towards a real-time game description language, W: ICAART 2016 : 8th International Conference on Agents and Artificial Intelligence, February 24-26, 2016, in Rome, Italy, Proceedings, Vol.2 / Jaap van den Herik, Joaquim Filipe (eds.). - [Setúbal] : SCITEPRESS , 2016. - S. 494-499. (http://dx.doi.org/10.5220/0005816904940499)
    9. M. Piotrów, Faster merging networks with a small constant period, Theoretical Computer Science. - Vol. 640 (2016) , s. 20-40. (http://dx.doi.org/10.1016/j.tcs.2016.05.038)
    10. M. V. Berlinkov, M. Szykuła, Algebraic synchronization criterion and computing reset words, Information Sciences. - Vol. 369 (2016), s. 718-730. (http://dx.doi.org/10.1016/j.ins.2016.07.049)
    11. M. Szykuła, V. Vorel, An extremal series of eulerian synchronizing automata, W: Developments in Language Theory : 20th International Conference, DLT 2016, Montréal, Canada, July 25-28, 2016, Proceedings / Srečko Brlek, Christophe Reutenauer (eds.). - Berlin, Heidelberg : Springer , 2016. - (Lecture Notes in Computer Science ; 9840).- S. 380-392. (http://dx.doi.org/10.1007/978-3-662-53132-7_31)
    12. J. Kowalski, M. Szykuła, Evolving chess-like games using relative algorithm performance profiles, W: Applications of Evolutionary Computation : 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 -- April 1, 2016, Proceedings, Part I / Giovanni Squillero, Paolo Burelli (eds.). - Cham : Springer International Publishing, 2016. - (Lecture Notes in Computer Science ; 9597).- S. 574-589. (http://dx.doi.org/10.1007/978-3-319-31204-0_37)
    13. J. Brzozowski, G. Jirásková, B. Liu, A. Rajasekaran, M. Szykuła, W: Descriptional Complexity of Formal Systems : 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings / Cezar Câmpeanu, Florin Manea, Jeffrey Shallit (eds.). - Cham : Springer International Publishing - Springer, 2016. - (Lecture Notes in Computer Science ; 9777).- S. 73-86. (http://dx.doi.org/10.1007/978-3-319-41114-9_6)
    14. P. Gawrychowski, A. Jeż, LZ77 factorisation of trees, W: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) / Akash Lal, S. Akshay, Saket Saurabh, Sandeep Sen (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. - (LIPIcs - Leibniz Internation Proceedings in Informatics ; 65).- S. 35:1-35:15. (http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2016.35)
    15. T. Jurdziński, D. R. Kowalski, Wake-up problem in multi-hop radio networks, W: Encyclopedia of Algorithms / Ming-Yang Kao (ed.). - New York : Springer, 2016. - S. 2352-2354. (http://dx.doi.org/10.1007/978-1-4939-2864-4_536)
    16. J. Brzozowski, G. Jirásková, B. Liu, A. Rajasekaran, M. Szykuła, On the state complexity of the shuffle of regular languages, W: Descriptional Complexity of Formal Systems : 18th IFIP WG 1.2 International Conference, DCFS 2016, Bucharest, Romania, July 5-8, 2016. Proceedings / Cezar Câmpeanu, Florin Manea, Jeffrey Shallit (eds.). - Cham : Springer International Publishing - Springer, 2016. - (Lecture Notes in Computer Science ; 9777).- S. 73-86. (http://dx.doi.org/10.1007/978-3-319-41114-9_6)

  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2015

    1. A. Jeż, Faster fully compressed pattern matching by recompression, ACM Transactions on Algorithms. - Vol. 11, iss.3 (2015), s. article no. 20. (http://dx.doi.org/10.1145/2631920).
    2. M. Bieńkowski, J. Byrka, T. Jurdziński, K.Chrobak, D. R. Kowalski, Provable fairness for TDMA scheduling, IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1, 2015, Proceedings. - Piscataway : IEEE, 2015.- S. 1320-1327. (http://dx.doi.org/10.1109/INFOCOM.2015.7218508).
    3. A. Jeż, Approximation of grammar-based compression via recompression, Theoretical Computer Science. - Vol. 592 (2015), s. 115-134. (http://dx.doi.org/10.1016/j.tcs.2015.05.027).
    4. A. Kisielewicz, J. Kowalski, M. Szykuła, Computing the shortest reset words of synchronizing automata, Journal of Combinatorial Optimization. - Vol. 29, iss. 1 (2015), s. 88-124. (http://dx.doi.org/10.1007/s10878-013-9682-0).
    5. M. Karpiński, M. Piotrów, Smaller selection networks for cardinality constraints encoding, Principles and Practice of Constraint Programming : 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015, Proceedings / Gilles Pesant (ed.). - Cham : Springer International Publishing , 2015. - (Lecture Notes in Computer Science ; 9255).- S. 210-225. (http://dx.doi.org/10.1007/978-3-319-23219-5_16).
    6. A. Kisielewicz, M. Szykuła, Synchronizing automata with extremal properties, Mathematical Foundations of Computer Science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella (eds.). - Berlin, Heidelberg : Springer Berlin, 2015. - (Lecture Notes in Computer Science ; 9234). - S. 331-343. (http://dx.doi.org/10.1007/978-3-662-48057-1_26).
    7. M. Berlinkov, M. Szykuła, Algebraic synchronization criterion and computing reset words, Mathematical Foundations of Computer Science 2015 : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part I / Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella (eds.). - Berlin, Heidelberg : Springer Berlin, 2015. - (Lecture Notes in Computer Science ; 9234).- S. 103-115. (http://dx.doi.org/10.1007/978-3-662-48057-1_8).
    8. M. Szykuła, Checking whether an automaton is monotonic is NP-complete, Implementation and Application of Automata : 20th International Conference, CIAA 2015, Umea, Sweden, August 18-21, 2015, Proceedings / Frank Drewes (ed.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9223).- S. 279-291. (http://dx.doi.org/10.1007/978-3-319-22360-5).
    9. J. Brzozowski, M. Szykuła, Complexity of suffix-free regular languages, Fundamentals of Computation Theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings / Adrian Kosowski, Igor Walukiewicz (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9210).- S. 146-159. (http://dx.doi.org/10.1007/978-3-319-22177-9_12).
    10. V. V. Gusev, M. Szykuła, On the number of synchronizing colorings of digraphs, Implementation and Application of Automata : 20th International Conference, CIAA 2015, Umea, Sweden, August 18-21, 2015, Proceedings / Frank Drewes (ed.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9223).- S. 127-139. (http://dx.doi.org/10.1007/978-3-319-22360-5_11).
    11. J. Brzozowski, M. Szykuła, Upper bound on syntactic complexity of suffix-free languages, Descriptional Complexity of Formal Systems : 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings / Jeffrey Shallit, Alexander Okhotin (eds.). - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 9118).- S. 33-45. (http://dx.doi.org/10.1007/978-3-319-19225-3_3).
    12. A. Kisielewicz, J. Kowalski, Testing general game players against a Simplified Boardgames player using temporal-difference learning, 2015 IEEE Congress on Evolutionary Computation, (CEC 2015), Sendai, Japan, May 25-28, 2015, Proceedings. - Piscataway : Institute of Electrical and Electronics Engineers, 2015. - S. 1466-1473. (http://dx.doi.org/10.1109/CEC.2015.7257061).
    13. T. Jurdziński, G. Stachowiak, Deterministic symmetry breaking in ring networks, 2015 IEEE 35th International Conference on Distributed Computing Systems (ICDCS 2015) ; Columbus, Ohio, USA, 29 June - 2 July 2015. - Piscataway, NJ : IEEE, 2015.- S. 517-526. (http://dx.doi.org/10.1109/ICDCS.2015.59).
    14. T. Jurdziński, M. Różański, G. Stachowiak, On setting-up asynchronous ad hoc wireless networks, 2015 IEEE Conference on Computer Communications (INFOCOM 2015) : Kowloon, Hong Kong, 26 April - 1 May 2015. - Piscataway, NJ : IEEE, 2015. - S. 2191 - 2199. (http://dx.doi.org/10.1109/INFOCOM.2015.7218605).
    15. T. Jurdziński, G. Stachowiak, The cost of synchronizing multiple-access channels, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing - PODC '15 . - New York : ACM , 2015.- S. 421-430. (http://dx.doi.org/10.1145/2767386.2767439).
    16. T. Jurdziński, D. R. Kowalski, K. Loryś, Online packet scheduling under adversarial jamming, Approximation and Online Algorithms : 12th International Workshop, WAOA 2014, Wrocław, Poland, September 11-12, 2014. - Cham : Springer International Publishing, 2015. - (Lecture Notes in Computer Science ; 8952). - S. 193-206. (http://dx.doi.org/10.1007/978-3-319-18263-6_17).
    17. A. Roman, M. Szykuła, Forward and backward synchronizing algorithms, Expert Systems with Applications. - Vol. 42, iss. 24 (2015), s. 9512-9527. (http://dx.doi.org/10.1016/j.eswa.2015.07.071).
    18. J. Brzozowski, M. Szykuła, Large aperiodic semigroups, International Journal of Foundations of Computer Science. - Vol. 26, iss. 07 (2015), s. 913-931. (http://dx.doi.org/10.1142/S0129054115400067).

  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2014

    1. P. Gawrychowski, Ł. Jeż, A. Jeż, Validating the Knuth-Morris-Pratt failure function, fast and online, Theory of Computing Systems. - Vol. 54, iss. 2 (2014), s. 337-372. (http://dx.doi.org/10.1007/s00224-013-9522-8).
    2. A. Jeż, M. Lohrey, Approximation of smallest linear tree grammar, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) / Ernst W. Mayr, Natacha Portier (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. - (LIPIcs - Leibniz International Proceedings in Informatics ; 25). - S. 445-457. (http://dx.doi.org/10.4230/LIPIcs.STACS.2014.445).
    3. A. Jeż, The complexity of compressed membership problems for finite automata, Theory of Computing Systems. - Vol.55, iss. 4 (2014), s. 685-718. (http://dx.doi.org/10.1007/s00224-013-9443-6).
    4. A. Jeż, Context unification is in PSPACE, Automata, languages, and programming : 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings. Part II / Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias (eds.). - Berlin, Heidelberg : Springer, 2014. - (Lecture Notes in Computer Science ; 8573). - S. 244-255. (http://dx.doi.org/10.1007/978-3-662-43951-7_21).
    5. A. Jeż, V. Diekert, W. Plandowski, Finding all solutions of equations in free groups and monoids with involution, Computer science - theory and applications : 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014 : proceedings / Edward A. Hirsch, Sergei O. Kuznetsov, Jean-Eric Pin, Nikolay K. Vereshchagin (eds.). - Cham : Springer, 2014. - (Lecture Notes in Computer Science ; 8476).- S. 1-15. (http://dx.doi.org/10.1007/978-3-319-06686-8_1).
    6. A. Jeż, A really simple approximation of smallest grammar, Combinatorial Pattern Matching : 25th Annual Symposium, CPM 2014, Moscow, Russia, June 16-18, 2014. Proceedings / Alexander S. Kulikov, Sergei O. Kuznetsov, Pavel Pevzner (eds.). - Cham : Springer, 2014. - (Lecture Notes in Computer Science ; 8486).- S. 182-191. (http://dx.doi.org/10.1007/978-3-319-07566-2_19).
    7. W. Bożejko, M. Karpiński, M. Pacut, M. Wodecki, Multi-GPU parallel memetic algorithm for capacitated vehicle routing problem, Parallel Processing and Applied Mathematics : 10th International Conference, PPAM 2013, Warsaw, Poland, September 8-11, 2013, Revised Selected Papers, Part 2 / Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, Jerzy Wasniewski (eds.). - Berlin : Springer Berlin, 2014. - (Lecture Notes in Computer Science ; 8385).- S. 207-214. (http://dx.doi.org/10.1007/978-3-642-55195-6_19).
    8. J. Brzozowski, M. Szykuła, Upper Bounds on Syntactic Complexity of Left and Two-Sided Ideals, In Developments in Language Theory (DLT 2014), volume 8633 of LNCS, pages 13-24.
    9. J. Brzozowski, M. Szykuła, Large Aperiodic Semigroups, In Implementation and Application of Automata (CIAA 2014), volume 8587 of LNCS, pages 124-135, 2014.
    10. A. Jeż, A. Okhotin, Computational completeness of equations over sets of natural numbers, Information and Computation 237 (2014), 56-94. (http://www.sciencedirect.com/science/article/pii/S0890540114000637)
    11. J. Kowalski, Embedding a Card Game Language into a General Game Playing Language, Frontiers in Artificial Intelligence and Applications Volume 264: STAIRS 2014, 161 - 170. (http://ebooks.iospress.nl/volumearticle/37205).
    12. W. Bożejko, M. Karpiński, M. Pacut, M. Wodecki, Multi-GPU Parallel Memetic Algorithm for Capacitated Vehicle Routing Problem, Lecture Notes in Computer Science No. 8386, Springer (2014), 207-214.
    13. T. Jurdziński, D. Kowalski, M. Różański, G. Stachowiak, On the Impact of Geometry on Ad Hoc Communication in Wireless Networks, 33rd ACM Symposium on Principles of Distributed Computing, PODC 2014, wydane w Proceedings of the 2014 ACM symposium on Principles of distributed computing, 2014, st. 357-366. (http://dl.acm.org/citation.cfm?doid=2611462.2611487).

  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2013

    1. M. Bieńkowski, M. Chrobak, C. Dürr, M. Hurand, Ł. Jeż, A. Jeż, G. Stachowiak, Collecting Weighted Items from a Dynamic Queue, Algorithmica, January 2013, Volume 65, Issue 1, pp 60-94. (http://dx.doi.org/10.1007/s00453-011-9574-6).
    2. M. Bieńkowski, M. Chrobak, C. Dürr, M. Hurand, Ł. Jeż, G. Stachowiak, A phi-competitive algorithm for collecting items with increasing weights from a dynamic queue, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 92-102. (http://dx.doi.org/10.1016/j.tcs.2012.12.046).
    3. P. Gawrychowski, Alphabetic minimax trees in linear time, Computer Science - Theory and Applications : 8th International Computer Science Symposium in Russia, CSR 2013, Ekaterinburg, Russia, June 25-29, 2013, Proceedings / Andrei A. Bulatov, Arseny M. Shur (eds.). - Berlin : Springer, 2013. - (Lecture Notes in Computer Science ; 7913). - S. 36-48. (http://dx.doi.org/10.1007/978-3-642-38536-0_4).
    4. A. Jeż, Approximation of grammar-based compression via recompression, Combinatorial pattern matching : 24th annual symposium, CPM 2013, Bad Herrenalb, Germany, June 17 - 19, 2013 / Johannes Fischer, Peter Sanders (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7922). - S. 165-176. (http://dx.doi.org/10.1007/978-3-642-38905-4).
    5. A. Jeż, One-variable word equations in linear time, Automata, languages, and programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, Part II / Fedor V. Fomin, Rusinš Freivalds, Marta Kwiatkowska, David Peleg (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7966). - S. 324-335. (http://dx.doi.org/10.1007/978-3-642-39212-2_30).
    6. A. Jeż, Recompression: a simple and powerful technique for word equations, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) / Natacha Portier, Thomas Wilke (eds.). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. - (LIPIcs - Leibniz International Proceedings in Informatics ; Vol.20). - S. 233-244. (http://dx.doi.org/10.4230/LIPIcs.STACS.2013.233)
    7. A. Jeż, Recompression: word equations and beyond, Developments in language theory : 17th international conference ; proceedings, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013 / Marie-Pierre Béal ; Oliver Carton (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7907). - S. 12-26. (http://dx.doi.org/10.1007/978-3-642-38771- 5_2).
    8. T. Jurdziński, D. R. Kowalski, G. Stachowiak, Distributed deterministic broadcasting in wireless networks of weak devices, Automata, languages, and programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8 - 12, 2013, Part II / Fedor V. Fomin, Rusinš Freivalds, Marta Kwiatkowska, David Peleg (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.7966). - S. 632-644. (http://dx.doi.org/10.1007/978-3- 642-39212-2_55).
    9. A. Kisielewicz, J. Kowalski, M. Szykuła, A fast algorithm finding the shortest reset words, 19th international conference ; proceedings / COCOON 2013, Hangzhou, China, June 21 - 23, 2013 / Ding-Zhu Du ; Guochuan Zhang (ed.). - Berlin ; Heidelberg : Springer, 2013. - (Lecture notes in computer science ; Vol.7936). - S. 182-196. (http://dx.doi.org/10.1007/978-3-642-38768-5_18).
    10. A. Kisielewicz, M. Szykuła, Generating small automata and the Černý conjecture, Implementation and Application of Automata : 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings / Stavros Konstantinidis (ed.). - Berlin, Heidelberg : Springer , 2013. - (Lecture Notes in Computer Science ; Vol.7982).- S. 340-348. (http://dx.doi.org/10.1007/978-3-642-39274-0_30).
    11. J. Kowalski, M. Szykuła, Game description language compiler construction, AI 2013: Advances in Artificial Intelligence : 26th Australian Joint Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings. - Cham : Springer International Publishing, 2013. - (Lecture Notes in Computer Science ; Vol.8272). - S. 234-245. (http://dx.doi.org/10.1007/978-3-319-03680-9_26).
    12. A. Jeż, A. Maletti, Hyper-minimization for deterministic tree automata, International Journal of Foundations of Computer Science. - Vol. 24, iss. 06 (2013), s. 815-830. (http://dx.doi.org/10.1142/S0129054113400200).
    13. T. Jurdziński, G. Stachowiak, Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks, Fundamentals of Computation Theory - 19th International Symposium (FCT 2013) : Springer, 2013. - (Lecture Notes in Computer Science ; Vol.8070). - s. 195-209. (http://dx.doi.org/10.1007/978-3-642-40164-0_20).
    14. T. Jurdziński, D. R. Kowalski, M. Różański, G. Stachowiak, Distributed Randomized Broadcasting in Wireless Networks under the SINR Model. Distributed Computing, 27th International Symposium (DISC 2013), : Springer 2013. - (Lecture Notes in Computer Science Volume 8205). s. 373-387. (http://dx.doi.org/10.1007/978-3-642-41527-2_26).
    15. P. Gawrychowski, D. Straszak, Beating O(nm) in Approximate LZW-Compressed Pattern Matching, 24th International Symposium, ISAAC 2013, Algorithms and Computation - Springer 2013 (Lecture Notes in Computer Science Vol. 8283, s. 78-88. (http://dx.doi.org/10.1007/978-3-642-45030-3_8).
    16. P. Gawrychowski, Optimal pattern matching in LZW compressed strings, ACM Transactions on Algorithms. - Vol. 9, iss.3 (2013), nr art. 25 (17 str.). (http://dx.doi.org/10.1145/2483699.2483705).
    17. A. Jeż, A. Okhotin, Unambiguous conjunctive grammars over a one-letter alphabet, Developments in Language Theory : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings / Marie-Pierre Béal, Olivier Carton (eds.). - Berlin, Heidelberg : Springer, 2013. - (Lecture notes in computer science ; 7907). - S. 277-288. ( http://www.dx.doi.org/10.1007/978-3-642-38771-5_25).

  • Publikacje Zakładu Złożoności Obliczeniowej i Algorytmów w roku 2012

    1. P. Gawrychowski, Tying up the loose ends in fully LZW-compressed pattern matching, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) / Christoph Dürr, Thomas Wilke (eds). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. - (LIPIcs - Leibniz International Proceedings in Informatics ; Vol. 14 ).- S. 624- 635. (http://dx.doi.org/10.4230/LIPIcs.STACS.2012.624).
    2. A. Jeż, Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P), 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) / Christoph Dürr, Thomas Wilke (eds). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. - (LIPIcs - Leibniz International Proceedings in Informatics ; Vol.14). - S. 136- 147. (http://dx.doi.org/10.4230/LIPIcs.STACS.2012.136).
    3. P. Gawrychowski, Faster algorithm for computing the edit distance between SLP-compressed strings, String Processing and Information Retrieval : 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012, Proceedings / Liliana Calderón- Benavides, Cristina González-Caro, Edgar Chávez,Nivio Ziviani (eds.). - Berlin : Springer Berlin , 2012. - (Lecture Notes in Computer Science ; 7608).- S. 229-236. (http://dx.doi.org/10.1007/978-3-642-34109-024).
    4. P. Gawrychowski, Simple and efficient LZW-compressed multiple pattern matching, Combinatorial pattern matching : 23rd annual symposium ; proceedings / CPM 2012, Helsinki, Finland, July 3 - 5, 2012 / Juha Karkkainen, Jens Stoye (eds.). - Berlin ; Heidelberg : Springer , 2012. - (Lecture Notes in Computer Science ; 7354).- S. 232-242. (http://dx.doi.org/10.1007/978-3-642-31265-619).
    5. A. Jeż, Faster fully compressed pattern matching by recompression, Automata, Languages, and Programming : 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I / ed. by Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, Roger Wattenhofer. - Berlin, Heidelberg : Springer, 2012. - (Lecture Notes in Computer Science ; 7391). - S. 533-544. (http://dx.doi.org/10.1007/978-3- 642-31594-7_45).
    6. A. Jeż, A. Okhotin, On the number of nonterminal symbols in unambiguous conjunctive grammars, Descriptional Complexity of Formal Systems : 14th International Workshop, DCFS 2012, Braga, Portugal, July 23-25, 2012 : proceedings / ed. by Martin Kutrib, Nelma Moreira, Rogério Reis. - Berlin, Heidelberg : Springer, 2012. - (Lecture Notes in Computer Science ; 7386). - S. 183-195. (http://dx.doi.org/10.1007/978-3-642-31623-4_14).
    7. A. Jeż, A. Maletti, Hyper-minimization for deterministic tree automata, Implementation and Application of Automata : 17th International Conference, CIAA 2012, Porto, Portugal, July 17-20, 2012 : proceedings / ed. by Nelma Moreira, Rogério Reis. - Berlin, Heidelberg : Springer Berlin Heidelberg, 2012. - (Lecture Notes in Computer Science ; 7381). - S. 217-228. (http://dx.doi.org/10.1007/978-3-642- 31606-7_19).
    8. C. Dürr, Ł. Jeż, N. K. Thang, Online scheduling of bounded length jobs to maximize throughput, Journal of Scheduling October 2012, Volume 15, Issue 5, pp 653-664 (http://dx.doi.org/10.1007/s10951-011-0233-1).
    9. Ł. Jeż, F. Li, J. Sethuraman, C. Stein, Online scheduling of packets with agreeable deadlines, Journal ACM Transactions on Algorithms (TALG) Volume 9 Issue 1, December 2012 Article No. 5, ACM New York, NY, USA (http://doi.acm.org/10.1145/2390176.2390181).
    10. L. Epstein, Ł. Jeż, J. Sgall, R. van Stee, Online Scheduling of Jobs with Fixed Start Times on Related Machines, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques Lecture Notes in Computer Science Volume 7408, 2012, pp 134-145 (http://dx.doi.org/10.1007/978-3-642-32512-0_12).
    11. A. Jeż, A. Okhotin, Representing hyper-arithmetical sets by equations over sets of integers, Theory of Computing Systems. - Vol. 51, nr 2 (2012), s. 196-228. (http://dx.doi.org/10.1007/s00224-011-9352-5).
    12. A. Jeż, T. Jurdziński, Length-reducing Automata (almost) without Auxiliary Symbols, Journal of Automata, Languages and Combinatorics, Otto-von-Guericke-Universitat, 16(2-4): 141-164 (2011); RK.
    13. T. Jurdziński, D. R. Kowalski, Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks, Distributed Computing - 26th International Sympodium (DISC 2012), LNCS 7611, Springer, 2012, 106-120; RK.
    14. T. Jurdziński, D. R. Kowalski, On the Complexity of Distributed Broadcasting and MDS Construction in Radio Networks, 16th International Conference On Principles Of Distributed Systems (OPODIS 2012), LNCS 7702, Springer, 2012, 209-224;RK.
    15. K. Paluch, K. Elbassioni, A. van Zuylen, Simpler approximation of the maximum asymmetric traveling salesman problem, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) / Christoph Dürr, Thomas Wilke (eds). - Wadern : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. - (LIPIcs - Leibniz International Proceedings in Informatics ; 14).- S. 501-506. (http://dx.doi.org/10.4230/LIPIcs.STACS.2012.501).
    16. K. Paluch, Faster and simpler approximation of stable matchings, Approximation and online algorithms : 9th international workshop ; revised selected papers : WAOA 2011, Saarbruecken, Germany, September 8-9, 2011 / (ed.)Roberto Solis-Oba, Giuseppe Persiano. - Berlin ; Heidelberg : Springer, 2012. - (Lecture Notes in Computer Science ; 7164). - S. 176-187.
    17. J. Byrka, K. Buchin, M. Buchin, M. Nöllenburg, Y. Okamoto, R. I. Silveira, Drawing (complete) binary tanglegrams : hardness, approximation, fixed-parameter tractability, Algorithmica. - Vol. 62, nr 1-2 (2012), s. 309-332. (http://dx.doi.org/10.1007/s00453-010-9456-3).
    18. M. Bieńkowski, T. Jurdziński, M. Korzeniowski, D. R. Kowalski, Distributed Online and Stochastic Queuing on a Multiple Access Channel, 26 Int. Symposum on DIStributed Computing (DISC), Lecture Notes in Computer Science vol. 7611, 121-135, 2012. (http://www.ii.uni.wroc.pl/~mbi/papers/2012-disc-online-mac.pdf).
    19. M. Bieńkowski, Migrating and Replicating Data in Networks Computer Science, Research and Development, vol. 27, issue 3, 169-179, 2012. Wyd.: Springer. (http://www.ii.uni.wroc.pl/~mbi/papers/2012-csrd-migration-replication-survey.pdf).
    20. M. Bieńkowski, J. Kutyłowski, The k-Resource Problem in Uniform Metric, Spaces, Theoretical Computer Science, vol. 459,42-54,2012. Wyd.: Elsevier. (http://www.sciencedirect.com/science/article/pii/S0304397512006214).