List of publications

Editorial work

  1. Maxime Crochemore and Leszek Gąsieniec (Editors),
    Matching Patterns, Hermes Science Publications, 2000, pp. 1-278.

  2. Paola Flocchini, Leszek Gąsieniec (Editors),
    13th International Colloquium Structural Information and Communication Complexity,
    LNCS 4056
    , SIROCCO 2006 , pp. 1-356.

  3. Andrzej Lingas and Leszek Gąsieniec (Editors),
    Foundations of Computation Theory (FCT 2003),
    Special issue of Theoretical Computer Science, 354(3) 2006, pp. 319-442.

Journals

  1. Amihood Amir, Leszek Gąsieniec and Riva Shalom,
    Improved approximate common interval,
    Information Processing Letters, 103(4) 2007, pp 142-149.

  2. Marek Chrobak, Leszek Gąsieniec, and Dariusz R. Kowalski,
    The Wake-Up Problem in MultiHop Radio Networks,
    SIAM Journal on Computing, 36(5) 2007, pp. 1453-1471.

  3. Leszek Gąsieniec, Aris Pagourtzis, Igor Potapov, and Tomasz Radzik,
    Deterministic Communication in Radio Networks with Large Labels,
    Algorithmica, 47(1) 2007, pp. 97-117.

  4. Leszek Gąsieniec, David Peleg, and Qin Xin,
    Faster communication in known topology radio networks,
    Distributed Computing, 19(4) 2007, pp. 289-300.

  5. • Leszek Gąsieniec, Chang Su, Prudence W.H. Wong, Qin Xin (2006) Routing of Single-source and Multiple-source Queries in Static Sensor Networks. Journal of Discrete Algorithms • Pierre Fraigniaud, Leszek Gąsieniec, Dariusz R. Kowalski, Andrzej Pelc (2006) Collective tree exploration. Networks vol 48 issue 3 pp 166-177 • Leszek Gąsieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin (2006) Deterministic M2M Multicast in Radio Networks. Theoretical Computer Science vol 362 issue 1-3 pp 196-206 • Robert Elsässer, Leszek Gąsieniec (2006) Radio communication in random graphs. Journal of Computer and System Sciences vol 72 issue 3 pp 490-506
  6. Peter Clote, Leszek Gąsieniec, Roman M. Kolpakov, Evangelos Kranakis, and Danny Krizanc,
    On realizing shapes in the theory of RNA neutral networks,
    Journal of Theoretical Biology, 236(2) 2005, pp. 216-227.

  7. L.Gąsieniec, R.M.Kolpakov, I.Potapov,
    Space efficient search for maximal repetitions,
    Theoretical Computer Science, 339(1) 2005, pp. 35-48.

  8. A.DeBonis, L.Gąsieniec, U.Vaccaro,
    Optimal Two-Stage Algorithms for Group Testing Problems,
    SIAM Journal on Computing, 34(5) 2005, pp. 1253-1270.

  9. M.Chrobak, L.Gąsieniec, and W.Rytter,
    A Randomized Algorithm for Gossiping in Radio Networks,
    Networks, 43(2) 2004, pp. 119-124.

  10. L.Gąsieniec, J.Jansson, and A.Lingas,
    Approximation algorithms for hamming clustering problems,
    Journal of Discrete Algorithms, 2(2) 2004, pp. 289-301.

  11. L.Gąsieniec and I.Potapov,
    Time/Space Efficient Compressed Pattern Matching,
    Fundamenta Informaticae, 56(1-2)
    2003, pp. 137-154.

  12. B.Chlebus, L.Gąsieniec, and A.Pelc
    Deterministic computations on a PRAM with Static Processor and Memory Faults,
    Fundamenta Informaticae, 55(3-4)
    2003, pp. 285-306.

  13. A.Czumaj, L. Gąsieniec, D.R.Gaur, R.Krishnamurti, W.Rytter, and M.Zito,
    Note: On Polynomial-time Approximation Algorithms for the Variable Length Scheduling Problem,
    Theoretical Computer Science, 302(1-3),
    2003, pp. 489-495.

  14. L.Gąsieniec and A.Lingas,
    On adaptive deterministic gossiping in ad hoc radio networks,
    Information Processing Letters 2(83),
    2002, pp. 89-94.

  15. M.Chrobak, L.Gąsieniec, and W.Rytter,
    Fast Broadcasting and Gossiping in Radio Networks,
    Journal of Algorithms 43(2),
    2002, pp. 177-189.

  16. B.S.Chlebus, L.Gąsieniec, A.Gibbons, A.Pelc, W.Rytter,
    Deterministic broadcasting in ad hoc radio networks,
    Distributed Computing 15(1),
    2002, pp. 27-38.

  17. L.Gąsieniec, A.Pelc, and D.Peleg,
    The Wakeup Problem in Synchronous Broadcast Systems,
    SIAM Journal on Discrete Mathematics 14(2),
    2001, pp. 207-222.

  18. A.Czumaj, I.Finch, L.Gąsieniec, A.Gibbons, P.Leng, W.Rytter, and M.Zito,
    Efficient web searching using temporal factors,
    Theoretical Computer Science, 262(1-2),
    2001, pp. 569-582.

  19. B.S.Chlebus, A.Czumaj, L.Gąsieniec, M.Kowaluk and W.Plandowski,
    Algorithms for the Parallel Alternating Direction Access Machine,
    Theoretical Computer Science, 245(2),
    2000, pp. 151--173.

  20. M.Crochemore, A.Czumaj, L.Gąsieniec, T.Lecroq, W.Plandowski, and W.Rytter,
    Practical muliti-pattern matching,
    Information Processing Letters, 71(3-4),
    1999, pp. 107--113.

  21. M.Crochemore, L.Gąsieniec, and W.Rytter,
    Constant-Space String-Matching in Sublinear Average Time,
    Theoretical Computer Science, 218(1),
    1999, pp. 197--203.

  22. L.Gąsieniec, E.Kranakis, D.Krizanc, and A.Pelc,
    Minimizing Congestion of Layouts for ATM Networks with Faulty Links,
    International Journal of Foundations of Computer Science, 10(4),
    1999, pp. 503-512.

  23. L.Gąsieniec, J.Jansson, A.Lingas, and A.Ostlin,
    On the Complexity of Constructing Evolutionary Trees,
    Journal of Combinatorial Optimization 3,
    1999, pp. 183--197.

  24. A.Czumaj, L.Gąsieniec, and A.Pelc,
    Time and cost trade-offs in gossiping,
    SIAM Journal on Discrete Mathematics, 11,
    1998, pp. 400--413.

  25. M.Crochemore, L.Gąsieniec, R.Hariharan, S.Muthukrishnan, and W.Rytter,
    A Constant Time Optimal Parallel Algorithm for Two Dimensional Pattern Matching,
    SIAM Journal on Computing, 27(3),
    1998, pp. 668--681.

  26. L.Gąsieniec and A.Pelc,
    Broadcasting with linearly bounded transmission faults,
    Discrete Applied Mathematics, 83,
    1998, pp. 121--133.

  27. M.Crochemore, Z.Galil, L.Gąsieniec, K.Park, and W.Rytter,
    Constant-Time Deterministic Sampling with Applications,
    SIAM Journal on Computing, 26(4),
    1997, pp. 950--960.

  28. A.Czumaj, L.Gąsieniec, M.Piotrow, and W.Rytter,
    Parallel and Sequential Approximation of the Shortest Superstring,
    Journal of Algorithms, 23,
    1997, pp. 74--100.

  29. L.Gąsieniec and A.Pelc,
    Broadcasting with a bounded fraction of faulty nodes,
    Journal of Parallel and Distributed Computing, 42,
    1997, pp. 11--20.

  30. L.Gąsieniec and A.Pelc,
    Adaptive broadcasting with faulty nodes,
    short communication in Parallel Computing, 22,
    1996, pp. 903--912.

  31. D.Breslauer and L.Gąsieniec,
    Efficient String Matching on Packed Texts,
    Informatique Theorique et Applications -- Theoretical Informatics and Applications, 30(6),
    1996, pp. 521--544.

  32. L.Gąsieniec, W.Plandowski, and W.Rytter,
    The zooming method: a recursive approach to time-space efficient string-matching,
    Theoretical Computer Science, 147,
    1995, pp. 19--30.

  33. M.Crochemore, A.Czumaj, L.Gąsieniec, S.Jarominek, T.Lecroq, W.Plandowski, and W.Rytter,
    Speeding up two string matching algorithms,
    Algorithmica 12,
    1994, pp.247--267.

  34. M.Crochemore, L.Gąsieniec, and W.Rytter,
    Two-dimensional pattern matching by sampling,
    Information Processing Letters, 46(2),
    1993, pp. 159--162.

Conference Proceedings

  1. R.Elsässer and L.Gąsieniec, Radio communication in random graphs; ©
    In Proceedings of 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'2005), pp. 309-315;

  2. B.S.Chlebus, L.Gąsieniec, D.R.Kowalski, T.Radzik, On the Wake-Up Problem in Radio Networks; ©
    In Proceedings of The 32nd International Colloquium on Automata, Languages and Programming (ICALP'2005), pp. 347-359;

  3. L.Gąsieniec, D.Peleg, and Q.Xin, Faster communication in known topology radio networks; ©
    In Proceedings of The 24th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'2005), pp. 129-137;

  4. L.Gąsieniec, R.Kolpakov, I.Potapov, and P.Sant, Real-time traversal in grammar-based compressed files; ©
    In Proceedings of The Data Compression Conference (Short Note) (DCC'2005), pp. 458;

  5. L.Gąsieniec, C.Su, P.Wong, and Q.Xin, Routing via Single-source and Multiple-source Queries in Static Sensor Networks; ©
    In Proceedings of 5th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN'2005);

  6. L.Gąsieniec, E.Kranakis, A.Pelc, and Q.Xin:
    Deterministic M2M Multicast in Radio Networks; ©
    In Proceedings of 31st International Colloquium on Automata, Languages and Programming (ICALP'2004), pp. 670-682;

  7. L.Gąsieniec, T.Radzik, and Q.Xin:
    Faster deterministic gossiping in directed ad-hoc radio networks; ©
    In Proceedings of 9th Scandinavian Workshop on Algorithm Theory (SWAT'2004), pp. 397-407;

  8. L.Gąsieniec and R.Kolpakov:
    Real-time string matching in sublinear space; ©
    In Proceedings of 15th Annual Combinatorial Pattern Matching Symposium (CPM'2004), pp. 117-129;

  9. L.Gąsieniec, I.Potapov, and Q.Xin:
    Time efficient gossiping in known radio networks; ©
    In Proceedings of 11th Colloquium on Structural Information and Communication Complexity (SIROCCO'2004), pp. 173-184;

  10. P.Fraigniaud, L.Gąsieniec, D.Kowalski, and A.Pelc:
    Collective tree exploration; ©
    In Proceedings of 6th Latin American (Symposium on) Theoretical Informatics (LATIN'2004), pp. 141-151;

  11. M.Chrobak, L.Gąsieniec and D.Kowalski:
    The Wake-Up problem in multi-hop radio networks; ©
    In Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2004), pp. 992-1000;

  12. L.Gąsieniec, R.Kolpakov, and I.Potapov:
    Space efficient search for maximal repetitions ©
    In Proceedings of 4th International Conference on Words (WORDS'03).;

  13. L.Gąsieniec and A.Lingas:
    An improved bound on Boolean matrix multiplication for highly clustered data ©
    In Proceedings of 8th International Workshop on Algorithms and Data Structures (WADS'03), pp 329-339;

  14. A.DeBonis, L.Gąsieniec, and U.Vaccaro:
    Generalized Framework for Selectors with Applications in Optimal Group Testing ©
    In Proceedings of 30th International Colloquium on Automata, Languages and Programming (ICALP'03), pp 81-96;

  15. B.S.Chlebus, L.Gąsieniec, D.Kowalski and A.A.Shvartsman:
    Bounding Work and Communication in Robust Cooperative Computation
    In Proceedings of 16th International Symposium on DIStributed Computing (DISC'02), pp 295-310;

  16. L.Gąsieniec, A.Pagourtzis and I.Potapov:
    Deterministic Communication in Radio Networks with Large Labels ©
    In Proceedings of 10th European Symposium on Algorithms (ESA'02), pp 512-524;

  17. L.Gąsieniec and I.Potapov:
    Gossiping with unit messages in known radio networks; ©
    In Proceedings of 2nd IFIP International Conference on Theoretical Computer Science (TCS'02), pp 193-205;

  18. M.Christersson, L.Gąsieniec, and A.Lingas:
    Gossiping with bounded size messages in ad-hoc radio networks; ©
    In Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP'02), pp 377-389;

  19. L.Gąsieniec and A.Lingas:
    On adaptive deterministic gossiping in ad hoc radio networks; ©
    In Proceedings of 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2002), pp 689-690;

  20. B.Chlebus, L.Gąsieniec, A.Lingas, and A.Pagourtzis,
    Oblivious gossiping in ad-hoc radio networks ©
    In Proceedings of 5th Int. Workshop on Discrete Algorithms and
    Methods for Mobile Computing and Communications
    , (DIALM'2001), pp 44-51;

  21. M.Chrobak, L.Gąsieniec, and W.Rytter,
    A Randomized Algorithm for Gossiping in Radio Networks; ©
    In Proceedings of 7th Annual International Computing and Combinatorics Conference, (COCOON'2001), pp 483-492;

  22. L.Gąsieniec and I.Potapov,
    Time/Space Efficient Compressed Pattern Matching; ©
    In Proceedings of 13th International Symposium on Fundamentals of Computation Theory, (FCT'2001), pp 138-149;

  23. P.Bose, J.Czyzowicz, L.Gąsieniec, E.Kranakis, D.Krizanc, A.Pelc, and M.Vargas Martin
    Strategies for Hotlink Assignments; ©
    In Proceedings of 11th Annual International Symposium on Algorithms and Computation , (ISAAC'2000), pp 23-34;

  24. M.Chrobak, L.Gąsieniec, and W.Rytter:
    Fast Broadcasting and Gossiping in Radio Networks; ©
    In Proceedings of 41st Annual Symposium on Foundations of Computer Science, (FOCS'2000), pp 575-581;

  25. L.Gąsieniec, A.Pelc, and D.Peleg:
    The Wakeup Problem in Synchronous Broadcast Systems; ©
    In Proceedings of 19th ACM Symposium on Principles of Distributed Computing (PODC'00), pp 113-121;

  26. B.Chlebus, L.Gąsieniec, A.Östlin, and M.Robson:
    Deterministic Radio Broadcasting; ©
    In Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP'00), pp 717-728;

  27. A.Czumaj and L.Gąsieniec:
    On the Complexity of Determining the Period of a String; ©
    In Proceedings of 11th Symposium on Combinatorial Pattern Matching (CPM'00), pp 412-422;

  28. L.Gąsieniec, J.Jansson and A.Lingas:
    Approximation Algorithms for Hamming Clustering Problem; ©
    In Proceedings of 11th Symposium on Combinatorial Pattern Matching (CPM'00), pp 108-118;

  29. B.Chlebus, L.Gąsieniec, A.Gibbons, A.Pelc and W.Rytter:
    Deterministic broadcasting in unknown radio networks; ©
    In Proceedings of 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00), pp 861-870;

  30. L.Gąsieniec, A.Gibbons and W.Rytter:
    On the fast parallel pattern-searching in texts with short description; ©
    In Proceedings of 24th International Symposium on Mathematical Foundations of Computer Science (MFCS'99), pp 48-58;

  31. L.Gąsieniec and W.Rytter:
    Searching patterns with short variables; ©
    In Proceedings of 10th Australasian Workshop on Combinatorial Algorithms (AWOCA'99) Perth, Western Australia, August 1999;

  32. G.Csizmadia, J.Czyzowicz, L.Gąsieniec, E.Kranakis and J.Urrutia:
    Domino Tilings of Orthogonal Polygons; ©
    In Proceedings of 11th Canadian Conference on Computational Geometry (CCCG'99), pp 158-161;

  33. A.Czumaj, I.Finch, L.Gąsieniec, A.Gibbons, P.Leng, W.Rytter and M.Zito:
    Efficient Web Searching Using Temporal Factors; ©
    In Proceedings of 6th Workshop on Algorithms and Data Structures (WADS'99), pp 294-305;

  34. L.Gąsieniec and W.Rytter:
    Almost optimal fully compresssed pattern matching; ©
    In Proceedings of Data Compression Conference (DCC'99), pp 316-325;

  35. L.Gąsieniec, J.Jansson and A.Lingas:
    Efficient Approximation Algorithms for the Hamming Center Problem; ©
    In Proceedings of Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pp 905-906;

  36. L.Gąsieniec, J.Jansson, A.Lingas and A.Östlin:
    Inferring Ordered Trees from Local Constraints; ©
    In Proceedings of Computing: the Australian Theory Symposium (CATS'98), pp 67-76;

  37. A.Czumaj, P.Ferragina, L.Gąsieniec, S. Muthukrishnan and J.Träff:
    The Architecture of a Software Library for String Processing; ©
    In Proceedings of Workshop on Algorithm Engineering (WAE'97), pp 294-305;

  38. L.Gąsieniec and P.Indyk:
    Efficient Parallel Computing with Memory Faults; ©
    In Proceedings of Fundamentals of Computation Theory, 11th International Symposium (FCT'97), pp 188-197;

  39. M.Crochemore, L.Gąsieniec, W.Rytter:
    Constant-Space String-Matching in Sublinear Average Time; ©
    In Proceedings of Compression and Complexity of Sequences (SEQUENCES'97), pp 230-239;

  40. G.Das, R.Fleischer, L.Gąsieniec, D.Gunopulos and J.Kärkkäinen :
    Episode Matching; ©
    In Proceedings of Combinatorial Pattern Matching, 8th Annual Symposium (CPM'97), pp 12-24;

  41. L.Gąsieniec, P.Indyk and P.Krysta:
    External Inverse Pattern Matching; ©
    In Proceedings of Combinatorial Pattern Matching, 8th Annual Symposium (CPM'97), pp 90-92;

  42. L.Gąsieniec, J.Jansson, A.Lingas and A.Östlin:
    On the complexity of computing evolutionary trees; ©
    In Proceedings of Computing and Combinatorics, 3rd Annual International Conference (COCOON'97), pp 134-145;

  43. L.Gąsieniec, E.Kranakis, D.Krizanc and A.Pelc:
    Minimizing Congestion of Layouts for ATM Networks with Faulty Links; ©
    In Proceedings of 21st International Symposium on Mathematical Foundations of Computer Science (MFCS'96), pp 372-381;

  44. B.Chlebus, A.Czumaj, L.Gąsieniec, M.Kowaluk and W.Plandowski:
    Parallel Alternating-Direction Access Machine; ©
    In Proceedings of 21st International Symposium on Mathematical Foundations of Computer Science (MFCS'96), pp 255-266;

  45. L.Gąsieniec, M.Karpinski, W.Plandowski and W.Rytter:
    Efficient Algorithms for Lempel-Ziv Encoding; ©
    In Proceedings of 5th Scandinavian Workshop on Algorithm Theory (SWAT'96), 392-403;

  46. G.Stolting Brodal and L.Gąsieniec:
    Approximate Dictionary Queries; ©
    In Proceedings of Combinatorial Pattern Matching, 7th Annual Symposium (CPM'96), pp 65-74;

  47. L.Gąsieniec, M.Karpinski, W.Plandowski and W.Rytter:
    Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach; ©
    In Proceedings of Combinatorial Pattern Matching, 7th Annual Symposium (CPM'96), pp 39-49;

  48. A.Czumaj, Z.Galil, L.Gąsieniec, K.Park and W.Plandowski:
    Work-Time Optimal Parallel Algorithms for String Problems; ©
    In Proceedings of 27th Annual ACM Symposium on Theory of Computing (STOC'95), pp 713-722;

  49. B.S.Chlebus, L.Gąsieniec and A.Pelc:
    Fast Deterministic Computations on a Faulty PRAM; ©
    In Proceedings of 3rd Annual European Symposium on Algorithms (ESA'95), pp 89-101;

  50. L.Gąsieniec, W.Plandowski and W.Rytter:
    The zooming method: a recursive approach to time-space efficient string-matching; ©
    Theoretical Computer Science, vol.147 (1995);

  51. D.Breslauer and L.Gąsieniec:
    Efficient String Matching on Coded Texts; ©
    In Proceedings of Combinatorial Pattern Matching, 6th Annual Symposium (CPM'95), pp 27-40;

  52. L.Gąsieniec, W.Plandowski and W.Rytter:
    Constant-space string matching with smaller number of comparisons: sequential sampling; ©
    In Proceedings of Combinatorial Pattern Matching, 6th Annual Symposium (CPM'95), pp 78-89;

  53. M.Crochemore, L.Gąsieniec, W.Plandowski and W.Rytter:
    Two-Dimensional Pattern Matching in Linear Time and Small Space;©
    In Proceedings of 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS'95), pp 181-192;

  54. L.Gąsieniec and K.Park:
    Work-Time Optimal Parallel Prefix Matching; ©
    In Proceedings of 2nd Annual European Symposium on Algorithms (ESA'94), pp 471-482;

  55. A.Czumaj, L.Gąsieniec, M.Piotrow and W.Rytter:
    Parallel and Sequential Approximation of Shortest Superstring; <©
    In Proceedings of 4th Scandinavian Workshop on Algorithm Theory (SWAT'94), pp 95-106;

  56. B.S.Chlebus and L.Gąsieniec:
    Optimal Pattern Matching on Meshes; ©
    In Proceedings of 11th Annual Symposium on Theoretical Aspects of Computer Science (STACS'94), pp 95-106;

  57. R.Cole, M.Crochemore, Z.Galil, L.Gąsieniec, R.Hariharan, S.Muthukrishnan, K.Park and W.Rytter:
    Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions; ©
    In Proceedings of 34th IEEE Symposium on Foundations of Computer Science (FOCS'93), pp 248-258;

  58. M.Crochemore, A.Czumaj, L.Gąsieniec, S.Jarominek, T.Lecroq, W.Plandowski, and W.Rytter:
    Optimal Pattern Matching on Meshes;
    In Proceedings of 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS'92), pp 589-600;

Other

  1. L.Gąsieniec:
    The Pseudo-Period Technique in Parallel String Matching; ©
    Dissertation, November (1994);

  2. L.Gąsieniec and A.Pelc:
    Broadcasting with a bounded fraction of faulty nodes; ©
    Tech. Rep., Quebec University, Hull, January (1995);

  3. L.Gąsieniec and A.Pelc:
    Adaptive broadcasting with faulty nodes; ©
    Tech. Rep., Quebec University, Hull, February (1995);

  4. L.Gąsieniec and A.Pelc:
    Broadcasting messages with linear faults; ©
    Tech. Rep., Quebec University, Hull, April (1995);

  5. A.Czumaj, L.Gąsieniec and A.Pelc:
    Time and cost trade-offs in gossiping; ©
    Tech. Rep., Quebec University, Hull, June (1995);

© Copyright Notice:
The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
leszek@csc.liv.ac.uk