List of publications
Editorial work
- Maxime Crochemore and Leszek Gąsieniec (Editors),
Matching Patterns, Hermes Science Publications,
2000, pp. 1-278.
- Paola Flocchini, Leszek Gąsieniec (Editors),
13th International Colloquium Structural Information and Communication Complexity,
LNCS 4056,
SIROCCO 2006 , pp. 1-356.
-
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
- Amihood Amir, Leszek Gąsieniec and Riva Shalom,
Improved approximate common interval,
Information Processing Letters, 103(4) 2007, pp 142-149.
- 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.
- 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.
- Leszek Gąsieniec, David Peleg, and Qin Xin,
Faster communication in known topology radio networks,
Distributed Computing, 19(4) 2007, pp. 289-300.
• 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
- 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.
- L.Gąsieniec, R.M.Kolpakov, I.Potapov,
Space efficient search for maximal repetitions,
Theoretical Computer Science, 339(1) 2005, pp. 35-48.
- 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.
- M.Chrobak, L.Gąsieniec, and W.Rytter,
A Randomized Algorithm for Gossiping in Radio Networks,
Networks, 43(2) 2004, pp. 119-124.
-
L.Gąsieniec, J.Jansson, and A.Lingas,
Approximation algorithms for hamming clustering problems,
Journal of Discrete Algorithms, 2(2) 2004, pp. 289-301.
-
L.Gąsieniec and I.Potapov,
Time/Space Efficient Compressed Pattern Matching,
Fundamenta Informaticae, 56(1-2)
2003, pp. 137-154.
-
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.
-
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.
-
L.Gąsieniec and A.Lingas,
On adaptive deterministic gossiping in ad hoc radio networks,
Information Processing Letters 2(83),
2002, pp. 89-94.
-
M.Chrobak, L.Gąsieniec, and W.Rytter,
Fast Broadcasting and Gossiping in Radio Networks,
Journal of Algorithms 43(2),
2002, pp. 177-189.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
L.Gąsieniec and A.Pelc,
Broadcasting with linearly bounded transmission faults,
Discrete Applied Mathematics, 83,
1998, pp. 121--133.
-
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.
-
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.
-
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.
-
L.Gąsieniec and A.Pelc,
Adaptive broadcasting with faulty nodes,
short communication in Parallel Computing, 22,
1996, pp. 903--912.
-
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.
-
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.
-
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.
-
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
- 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;
- 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;
- 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;
- 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;
- 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);
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- L.Gąsieniec, R.Kolpakov, and I.Potapov:
Space efficient search for maximal repetitions ©
In Proceedings of
4th International Conference on Words
(WORDS'03).;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- L.Gąsieniec and W.Rytter:
Almost optimal fully compresssed pattern matching;
©
In Proceedings of
Data Compression Conference
(DCC'99), pp 316-325;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- G.Stolting Brodal and L.Gąsieniec:
Approximate Dictionary Queries;
©
In Proceedings of
Combinatorial Pattern Matching, 7th Annual Symposium
(CPM'96), pp 65-74;
- 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;
- 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;
- 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;
- 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);
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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;
- 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
- L.Gąsieniec:
The Pseudo-Period Technique in Parallel String Matching;
©
Dissertation, November (1994);
- L.Gąsieniec and A.Pelc:
Broadcasting with a bounded fraction of faulty nodes;
©
Tech. Rep., Quebec University, Hull, January (1995);
- L.Gąsieniec and A.Pelc:
Adaptive broadcasting with faulty nodes;
©
Tech. Rep., Quebec University, Hull, February (1995);
- L.Gąsieniec and A.Pelc:
Broadcasting messages with linear faults;
©
Tech. Rep., Quebec University, Hull, April (1995);
- A.Czumaj, L.Gąsieniec and A.Pelc:
Time and cost trade-offs in gossiping;
©
Tech. Rep., Quebec University, Hull, June (1995);
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