Jiri Sgall - Publications

Most of my papers are available in postscript or PDF format. To get them by e-mail, or to send me any comments, write me at last name at iuuk.mff.cuni.cz.

Papers are sorted roughly in the reverse order of their writing, in each of the areas:

Note: The on-line versions of journal papers are the versions accepted to publication, which do not reflect the last changes. Papers not published in a journal are usually newer versions than the conference paper or the technical report. Copyright for the published version is usually with the publisher, consequently any use beyond personal and academic use (as typically allowed by the publisher's rules) requires a permission.

Surveys and book chapters

J. Sgall: Online preemptive scheduling on parallel machines
In Ming-Yang Kao, editor, Encyclopedia of Algorithms, 2nd edition, pages 1461-1464. Springer. 2016.

J. Sgall: Online bin packing: Old algorithms and new results
In Proc. of the 10th Conference on Computability in Europe (CiE), Lecture Notes in Comput. Sci., pages 362-372. Springer, 2014.

J. Sgall: Open problems in throughput scheduling
Proc. of the 20th Ann. European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 7501, pages 2-11. Springer, 2012.

K. Pruhs, E. Torng, J. Sgall: Online scheduling
In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, ed. Joseph Y.-T. Leung, chapter 15, pages 15-1 - 15-41, CRC Press, 2004.

J. Sgall: Probabilistic Proofs and NP-completeness (A Course on the PCP Theorem and its Consequences)
Technical report ITI Series 2002-088, Charles University, Prague, 2002.

J. Sgall: On-line scheduling
In Online Algorithms: The State of the Art, eds.A. Fiat and G. J. Woeginger, Lecture Notes in Comput. Sci. 1442, pages 196-231, Springer, 1998.

J. Sgall: On-line scheduling of parallel jobs
In Proc. of the 19th Mathematical Foundations of Comput. Sci. (MFCS) , Lecture Notes in Comput. Sci. 841, pages 159-176. Springer, 1994.

On-line and approximation algorithms, scheduling

M. Bohm, L. Jez, J. Sgall, and P. Vesely: On Packet Scheduling with Adversarial Jamming and Speedup
To appear in Proc. of the 15th Workshop on Approximation and Online Algorithms (WAOA 2017), Lecture Notes in Comput. Sci. ???, pages ???, Springer, 2018. Also arXiv:1705.07018.

M. Bienkowski, M. Bohm, L. Jez, P. Laskos-Grabowski, J. Marcinkowski, J. Sgall, A. Spyra and P. Vesely: Logarithmic price of buffer downscaling on line metrics
To appear in Theor. Comput. Sci. Also arXiv:1610.04915.

M. Bohm, M. Chrobak, L. Jez, F. Li, J. Sgall, and P. Vesely: Online Packet Scheduling with Bounded Delay and Lookahead
In Proc. of the 27th International Symposium on Algorithms and Computation (ISAAC), LIPIcs vol. 64, pages 21:1-21:13, Schloss Dagstuhl, 2016.
Full version submitted.

M. Bienkowski, M. Bohm, J. Byrka, M. Chrobak, C. Durr, L. Folwarczny, L. Jez, J. Sgall, Nguyen Kim Thang, and P. Vesely:
Online Algorithms for Multi-Level Aggregation
In Proc. of the 24th Ann. European Symp. on Algorithms (ESA), LIPIcs vol. 57, pages 12:1-12:17, Schloss Dagstuhl, 2016.
Full version submitted.

M. Bohm, J. Sgall, R. van Stee, and P. Vesely: Online bin stretching with three bins
To appear in J. Sched. Online available as DOI 10.1007/s10951-016-0504-y, 2017.
arXiv:1404.5569v3, 2016. 

M. Bohm, J. Sgall, R. van Stee, and P. Vesely: A two-phase algorithm for bin stretching with stretching factor 1.5
J. of Combinatorial Optimization 34(3): 810-828, 2017. DOI 10.1007/s10878-017-0114-4, 2017.
Also arXiv:1601.08111v2.

M. Bohm, Gy. Dosa, L. Epstein, J. Sgall, and P. Vesely: Colored Bin Packing: Online Algorithms and Lower Bounds
Submitted.
To appear in Algorithmica. Online available as DOI 10.1007/s00453-016-0248-2, 2017.

L. Folwarczny, J. Sgall: General Caching Is Hard: Even with Small Pages
Algorithmica 79(2):319–339, 2017. DOI 10.1007/s00453-016-0185-0.
A preliminary version appeared in Proc. of the 26th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Comput. Sci. 9472, pages 116-126, Springer, 2015.

E. Althaus, A. Brinkmann, P. Kling, F. Meyer auf der Heide, L. Nagel, S. Riechers, J. Sgall, T. Suss:
Scheduling Shared Continuous Resources on Many-Cores
To appear in J. Sched. Online available as DOI 10.1007/s10951-017-0518-0, 2017.

J. Balogh, J. Bekesi, Gy. Dosa, J. Sgall, and R. van Stee: The optimal absolute ratio for online bin packing
In Proc. of the 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA). Pages 1425-1438. ACM-SIAM, 2015.

M. Bohm, J. Sgall, R. van Stee, P. Vesely: Better algorithms for online bin stretching
In Proc. of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Comput. Sci. 8952, pages 23-34, Springer, 2015.

M. Bohm, J. Sgall, P. Vesely: Online colored bin packing
In Proc. of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Comput. Sci. 8952, pages 35-46, Springer, 2015.

J. Sgall, G. J. Woeginger: Multiprocessor jobs, preemptive schedules, and one-competitive online algorithms
In Proc. of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014), Lecture Notes in Comput. Sci. 8952, pages 236-247, Springer, 2015.

M. Cygan, L. Jez, J. Sgall: Online knapsack revisited
Theory Comput. Syst. 58(1):153-190, 2016.

Gy. Dosa, J. Sgall: Optimal analysis of Best Fit bin packing
Proc. of the 31st Int. Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 8572, pages 429-441, Springer, 2014.

M. Bienkowski, J. Byrka, M. Chrobak, L. Jez, D. Nogneng, J. Sgall: Better approximation bounds for the joint replenishment problem
Proc. of the 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 42-54. ACM-SIAM, 2014.

M. Bienkowski, J. Byrka, M. Chrobak, L. Jez, J. Sgall, G. Stachowiak: Online control message aggregation in chain networks
Proc. of the 13th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Comput. Sci. 8037, pages 133-145. Springer, 2013.

Gy. Dosa, J. Sgall: First Fit bin packing: A tight analysis
Proc. of the 30th Ann. Symp. on Theor. Aspects of Comput. Sci. (STACS), LIPIcs vol. 20, pages 538-549. Schloss Dagstuhl, 2013.

L. Jez, J. Schwartz, J. Sgall, and J. Bekesi: Lower bounds for online makespan minimization on a small number of related machines
J. Sched. 16(5):539-547, 2013.
The results of numerical calculations described in the paper.

L. Epstein, L. Jez, J. Sgall, and R. van Stee: Online scheduling of jobs with fixed start times on related machines
Algorithmica 74(1):156-176, 2016.
A preliminary version appeared in Proc. of the 15th APPROX and 16th RANDOM, Lecture Notes in Comput. Sci. 7408, pages 134-145. Springer, 2012.

J. Sgall: A new analysis of Best Fit bin packing
Proc. of the 6th Int. Conference Fun with Algorithms (FUN), Lecture Notes in Comput. Sci. 7288, pages 315-321. Springer, 2012.

T. Ebenlendr, J. Sgall: A lower bound on deterministic online algorithms for scheduling on related machines without preemption
Theory Comput. Syst. 56(1):73-81, 2015.
A preliminary version appeared in Proc. of the 9th Workshop on Approximation and Online Algorithms (WAOA 2011), Lecture Notes in Comput. Sci. 7164, pages 102-108, Springer, 2012.

M. Chrobak, J. Sgall, G. J. Woeginger: Two-Bounded-Space Bin Packing Revisited
Proc. of the 19th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 6942, pages 263-274, Springer, 2011.

M. Chrobak, L. Jez, J. Sgall: Better Bounds for Incremental Frequency Allocation in Bipartite Graphs
Theoretical Comput. Sci., 514:75-83, 2013.
A preliminary version appeared in Proc. of the 19th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 6942, pages 251-262, Springer, 2011.

O. Zajicek, J. Sgall, T. Ebenlendr: Online scheduling of parallel jobs on hypercubes: Maximizing the throughput
Proc. of the Parallel Processing and Applied Mathematics (PPAM'09), Part II, Lecture Notes in Comput. Sci. 6068, pages 52-61, Springer, 2010.

M. Chrobak, J. Sgall: Three results on frequency assignment in linear cellular networks
Theoretical Comput. Sci., 411(1):131-137, 2010.
A preliminary version appeared in Proc. of the 5th Int. Conf. Algorithmic Aspects in Information and Management (AAIM),  Lecture Notes in Comput. Sci. 5564, pages 129-139, Springer, 2009.

T. Ebenlendr, J. Sgall: A lower bound for scheduling of unit jobs with immediate decision on parallel machines
Proc. of the 6th Workshop on Approximation and Online Algorithms (WAOA 2008), Lecture Notes in Comput. Sci. 5426, pages 43-52, Springer, 2009.

T. Ebenlendr, J. Sgall: Semi-online preemptive scheduling: One algorithm for all variants
Theory Comput. Syst., 48(3):577-613, 2011.
A preliminary version appeared in Proc. of the 26th Ann. Symp. on Theor. Aspects of Comput. Sci. (STACS), LIPIcs vol. 3, pages 349-360, Schloss Dagstuhl, 2009.
The results of numerical calculations described in the paper.

H. Bruhn, J. Cerny, A. Hall, P. Kolman, J. Sgall: Single source multiroute flows and cuts on uniform capacity networks
Theory of Computing, 4:1-20, 2008.

T. Ebenlendr, M. Krcal, J. Sgall: Graph balancing: A special case of scheduling unrelated parallel machines
Algorithmica. 68(1): 62-80, 2014.
A preliminary version appeared in Proc. of the 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 483-490, ACM-SIAM, 2008.

J. Ding, T. Ebenlendr, J. Sgall, G. Zhang: Online scheduling of equal-length jobs on parallel machines
Proc. of the 15th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 4698, pages 427-438. Springer, 2007.

M. Chrobak, M. Hurand, J. Sgall: Fast algorithms for testing fault-tolerance of sequenced jobs with deadlines
J. Sched.,12(5):501-515, 2009.
A preliminary version appeared in Proc. of the 28th IEEE Real-Time Systems Symposium (RTSS), pages 139-148. IEEE, 2007.

T. Ebenlendr, W. Jawor, J. Sgall: Preemptive Online Scheduling: Optimal Algorithms for All Speeds
Algorithmica, 53(4):504-522, 2009.
A preliminary version appeared in Proc. of the 14th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 4168, pages 327-339, Springer, 2006.
The results of numerical calculations described in the paper.

L. Epstein, Y. Kleiman, J. Sgall, R. van Stee: Paging with connections: FIFO strikes again
Theoretical Comput. Sci., 377(1-3):55-64, 2007.

T. Ebenlendr, J. Noga, J. Sgall, G. Woeginger: A note on semi-online machine covering
Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), Lecture Notes in Comput. Sci. 3879, pages 110-118, Springer, 2006.

J. Sgall, H. Shachnai, T. Tamir: Fairness-Free Periodic Scheduling with Vacations
Theoretical Comput. Sci., 410(47-49): 5112-5121, 2009.
A preliminary version appeared in Proc. of the 13th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 3669, pages 592-603, Springer, 2005.

M. Chrobak, P. Kolman, J. Sgall: The greedy algorithm for the minimum common string partition problem
ACM Trans. on Algorithms, 1(2):350-366, 2005.
A preliminary version appeared in Proc. of the APPROX, Lecture Notes in Comput. Sci. 3122, pages 84-95, Springer, 2004.

M. Chrobak, W. Jawor, J. Sgall, T. Tichy: Online scheduling of equal-length jobs: Randomization and restarts help
SIAM J. Comput., 36(6):1709-1728, 2007.
A preliminary version appeared in Proc. of the 31st Int. Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 3142, pages 358-370, Springer, 2004.

M. Chrobak, W. Jawor, J. Sgall, T. Tichy: Improved online algorithms for buffer management in QoS switches
ACM Trans. on Algorithms, 4(3):Article No. 50, 2007.
A preliminary version appeared in Proc. of the 12th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 3221, pages 204-215, Springer, 2004.

M. Blaser, B. Manthey, J. Sgall: An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
J. of Discrete Algorithms, 4(4):623-632, 2006.

T. Ebenlendr, J. Sgall: Optimal and online preemptive scheduling on uniformly related machines
J. Sched., 12(5):517-527, 2009.
A preliminary version appeared in Proc. of the 21st Ann. Symp.  on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci. 2996, pages 199-210. Springer, 2004.

F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, T. Tichy: Online competitive algorithms for maximizing weighted throughput of unit jobs
J. of Discrete Algorithms, 4(2):255-276, 2006.
A preliminary version appeared in Proc. of the 21st Ann. Symp.  on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci., pages 187-198. Springer, 2004; authors included also Y. Bartal and R. Lavi.

M. Chrobak, J. Sgall:
Analysis of the Harmonic Algorithm for Three Servers
In Proc. of the 20th Ann. Symp. on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci. 2607, pages 247-259. Springer, 2003.
Unfortunately, this paper contains an error which seems to be irrepairable.

M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tichy, N. Vakhania: Preemptive scheduling in overloaded systems
J. Comput. Syst. Sci., 67(1):183-197, 2003.
A preliminary version appeared in Proc. of the 29th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 2380, pages 800-811, Springer, 2002.

W. E. de Paepe, J. K. Lenstra, J. Sgall, R. A. Sitters, L. Stougie: Computer-Aided Complexity Classification of Dial-a-Ride Problems
INFORMS J. on Computing, 16(2):120-132, 2004.

M. Chrobak, J. Sgall: Algorithms for Testing Fault-Tolerance of Sequenced Jobs
Technical report UCR-CS-00-06, UC Riverside, 2000.

M. Chrobak, J. Csirik, C. Imreh, J. Noga, J. Sgall,  G. J. Woeginger: The buffer minimization problem for multiprocessor scheduling with conflicts
In Proc. of the 28th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Comput. Sci. 2076, pages 862-874, Springer, 2001.

M. Chrobak, J. Sgall: The weighted 2-server problem
Theoretical Comput. Sci., 324(2-3):289-319, 2004.
A preliminary version appeared in Proc. of the 17th Ann. Symp. on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci. 1770, pages 593-604. Springer, 2000.

M. Chrobak, J. Sgall: A simple analysis of the harmonic algorithm for two servers
Inf. Process. Lett., 75(1-2):75-77, 2000.

Y. Azar, O. Regev, J. Sgall,  G. J. Woeginger: Off-line temporary tasks assignment
Theoretical Comput. Sci., 287(2):419-428, 2002.

L. Epstein, J. Sgall: A lower bound for on-line scheduling on uniformly related machines
Oper. Res. Lett., 26(1):17-22, 2000.

L. Epstein, J. Sgall: Approximation schemes for scheduling on uniformly related and identical parallel machines
Algorithmica, 39(1):43-57, 2004.
A preliminary version appeared in Proc. of the 7th European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 1643, pages 151-162, Springer, 1999.

S. Seiden, J. Sgall, G. J. Woeginger: Semi-online scheduling with decreasing job sizes
Oper. Res. Lett., 27(5):215-221, 2000.

L. Epstein, J. Noga, S. Seiden, J. Sgall, G. J. Woeginger: Randomized online scheduling on two uniform machines
J. of Scheduling, 4(2):71-92, 2001.
A preliminary version appeared in Proc. of the 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) , pages 317-326, ACM-SIAM, 1999.

A. Avidor, Y. Azar, J. Sgall: Ancient and new algorithms for load balancing in the Lp norm
Algorithmica, 29(3):422-441, 2001.
A preliminary version appeared in Proc. of the 9th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) , pages 426-435. ACM-SIAM, 1998.

Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, L. Stougie: Multiprocessor scheduling with rejection
SIAM J. Disc. Math., 13(1):64-78, 2000.
A preliminary version appeared in Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA) , pages 95-103. ACM-SIAM, 1996.

J. Sgall: A lower bound for randomized on-line multiprocessor scheduling
Inf. Process. Lett., 63(1):51-55, 1997.

A. Feldmann, B. Maggs, J. Sgall, D. D. Sleator, A. Tomkins: Competitive analysis of call admission algorithms that allow delay
Technical report CMU-CS-95-102, Carnegie-Mellon University, 1995.

J. Sgall: Randomized on-line scheduling of parallel jobs
J. of Algorithms, 21:149-175, 1996.
A preliminary version appeared in Proc. of the 3rd Israel Symp. on Theory of Computing and Systems (ISTCS) , 241-150, IEEE, 1995.

J. Sgall: On-Line Scheduling on Parallel Machines. PhD thesis.
Technical report CMU-CS-94-144, Carnegie-Mellon University, Pittsburgh, PA, U.S.A., 1994.

A. Feldmann, M.-Y. Kao, J. Sgall, S.-H. Teng: Optimal online scheduling of parallel jobs with dependencies
J. of Combinatorial Optimization, 1(4):393-411, 1998.
A preliminary version appeared in Proc. of the 25th Ann. ACM Symp. on Theory of Computing (STOC), pages 642-651. ACM, 1993.

A. Feldmann, J. Sgall, S.-H. Teng: Dynamic scheduling on parallel machines
Theoretical Comput. Sci., 130(1):49-72, 1994.
A preliminary version appeared in Proc. of the 32nd Ann. IEEE Symp. on Foundations of Computer Sci. (FOCS), 111-120, IEEE, 1991.

Complexity and combinatorics

D. Kral, T. Tichy, J. Sgall: Randomized Strategies for the Plurality Problem
Discrete Applied Mathematics,156(17):3155-3338, 2008.

J. Sima, J. Sgall: On the Non-Learnability of a Single Spiking Neuron
Neural Computation,17(12):2635-2647, 2005.

T. Feder, P. Hell, D. Kral, J. Sgall: Two algorithms for general list matrix partitions
In Proc. of the 16th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 870-876, ACM-SIAM, 2005.

A. Bagchi, A. Chaudhary, P. Kolman, J. Sgall: A simple combinatorial proof of duality of multiroute flows and cuts
KAM-DIMATIA Series 2004-662 and ITI Series 2004-186, Charles University, Prague, 2004.

D. Kral, J. Sgall: Coloring graphs from lists with bounded size of their union
J. of Graph Theory, 49(3):177-186, 2005.

E. Fischer, I. Newman, J. Sgall: Functions that have read-twice constant width branching programs are not necessarily testable
Random Structures and Algorithms, 24(2):175-193, 2004.

G. J. Woeginger, J. Sgall: The complexity of coloring graphs without long induced paths
Acta Cybernetica, 15(1):107-117, 2001.

J. Sgall: Bounds on pairs of families with restricted intersections
Combinatorica, 19(4):555-566, 1999.

P. Savicky, J. Sgall:
DNF tautologies with a limited number of occurrences of every variable
Theoretical Comput. Sci., 238(1-2):495-498, 2000.

R. Impagliazzo, P. Pudlak, J. Sgall:
Lower bounds for the polynomial calculus and the Groebner basis algorithm
Comput. Complexity, 8(2):127-144, 1999.

P. Pudlak, J. Sgall:
Algebraic models of computation and interpolation for algebraic proof systems
In Proof Complexity and Feasible Arithmetic, ed. P. W. Beame and S. R. Buss, DIMACS Series in Discrete Mathematics and Theor. Comp. Sci., volume 39, pages 279-296, AMS, 1998.

S. Buss, R. Impagliazzo, J. Krajicek, P. Pudlak, A. A. Razborov, J.Sgall:
Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
Comput. Complexity, 6(3):256-298, 1996/1997.

C. Damm, S. Jukna, J. Sgall:
Some bounds for multiparty communication complexity of pointer jumping
Comput. Complexity, 7(2):109-127, 1998.
A preliminary version appeared in Proc. of the 13th Ann. Symp. on Theor. Aspects of Comput. Sci. (STACS), Lecture Notes in Comput. Sci. 1046, pages 643-654. Springer, 1996.

P. Pudlak, J. Sgall: An upper bound for a communication game related to space-time tradeoffs
In The Mathematics of Paul Erdos, volume I, eds. Ronald L. Graham and Jaroslav Nesetril, pages 393-399. Springer, 1996.

P. Pudlak, V. Rodl, J. Sgall: Boolean circuits, tensor ranks and communication complexity
SIAM J. Comput., 26(3):605-633, 1997.

J. Sgall: Solution of a covering problem related to labelled tournaments
J. of Graph Theory, 23(2):111-118, 1996.

J. Edmonds, R. Impagliazzo, S. Rudich, J. Sgall: Communication complexity towards lower bounds on circuit depth
Comput. Complexity, 10(3):210-246, 2001/2002.
A preliminary version appeared in Proc. of the 32nd Ann. IEEE Symp. on Foundations of Computer Sci. (FOCS), pages 249-257. IEEE, 1991.

J. Krajicek, P. Pudlak, J. Sgall: Interactive computations of optimal solutions
In Proc. of the 15th Mathematical Foundations of Comput. Sci. (MFCS) , Lecture Notes in Comput. Sci. 452, pages 48-60. Springer, 1990.

I. Kriz, J. Sgall: Well-quasi-ordering depends on labels
Acta Scientarium Mathematicarum, 55:55-69, 1991.

Other areas

G. J. Woeginger, J. Sgall: On the complexity of cake cutting
Discrete Optimization, 4(2):213-220, 2007.
Another related paper, containing the remaining part of the material of the preliminary version (the link above), was published as: J. Sgall, G. J. Woeginger: An approximation scheme for cake division with a linear number of cuts, Combinatorica, 27(2):205-211, 2007. However, I had nothing to do with that part, and my name appears on it only due to Gerhard's generosity.

J. Sgall, G. J. Woeginger: A lower bound for cake cutting
In Proc. of the 11th Ann. European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 2832, pages 459-469, Springer, 2003.

D. Kral, V. Majerech, T. Tichy, J. Sgall,  G. J. Woeginger: It is tough to be a plumber
Theoretical Comput. Sci., 313(3):473-484, 2004.

J. Sgall: A solution of David Gale's man and lion problem
Theoretical Comput. Sci., 259(1-2):663-670, 2001.

E. Anderson, M. Chrobak, J. Noga, J. Sgall, G. J. Woeginger: Solution of a problem in DNA computing
Theoretical Comput. Sci., 287(2):387-391, 2002.

O. Berkman, M. Parnas, J. Sgall: Efficient dynamic traitor tracing
SIAM J. Comput., 30(6):1802-1828, 2001.
A preliminary version appeared in Proc. of the 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 586-595, ACM-SIAM, 2000.

D. Boneh, C. Dunworth, Richard J. Lipton, J. Sgall: Making DNA computers error resistant
DNA Based Computers II (Princeton University, NJ, 1996), 163-170, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 44, Amer. Math. Soc., Providence, RI, 1999.

D. Boneh, C. Dunworth, Richard J. Lipton, J. Sgall: On the computational power of DNA
Discrete Applied Mathematics, 71:79-94, 1996.

J. Sgall, A. Sochor: Revealed automorphisms
Commentationes Mathematicae Universitatis Carolinae, 32(1):105-113, 1991.

J. Sgall, A. Sochor: Forcing in the alternative set theory II
Commentationes Mathematicae Universitatis Carolinae, 32(2):339-353, 1991.

J. Sgall: Forcing in the alternative set theory I
Commentationes Mathematicae Universitatis Carolinae, 32(2):323-337, 1991.

J. Sgall, J. Witzany: Dimension of indiscernibility equivalences
Commentationes Mathematicae Universitatis Carolinae, 28(3):537-547, 1987.

J. Sgall: Construction of the class FN
Commentationes Mathematicae Universitatis Carolinae, 27(3):435-436, 1986.

M. Platek, J. Sgall, P. Sgall: A dependency base for a linguistic description
In Contributions to Functional Syntax, Semantics Language Comprehension. Benjamins, 1984.

(last update: August 2017)