If you made any changes in Pure these will be visible here soon.

Publications 2003 2018

2018

Counting connected subgraphs with maximum-degree-aware sieving

Bjorklund, A., Husfeldt, T., Kaski, P. & Koivisto, M. K. H., 2018, 29th International Symposium on Algorithms and Computation (ISAAC 2018). Hsu, W-L., Lee, D-T. & Liao, C-S. (eds.). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 17:1-17:12 12 p. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

On the number of connected sets in bounded degree graphs

Kangas, K., Kaski, P., Korhonen, J. H. & Koivisto, M., 16 Nov 2018, In : The Electronic Journal of Combinatorics. 25, 4, 19 p., P4.34.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., Feb 2018, In : IEEE Transactions on Information Theory. 64, 2, p. 1368-1373 6 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
2017

Narrow sieves for parameterized paths and packings

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., Aug 2017, In : Journal of Computer and System Sciences. 87, p. 119-139 21 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
2016

Fast Zeta Transforms for Lattices with Few Irreducibles

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M., Nederlof, J. & Parviainen, P., Feb 2016, In : ACM Transactions on Algorithms. 12, 1, 19 p., 4.

Research output: Contribution to journalArticleScientificpeer-review

Separating OR, SUM, and XOR Circuits

Find, M., Göös, M., Järvisalo, M., Kaski, P., Koivisto, M. & Korhonen, J. H., Aug 2016, In : Journal of Computer and System Sciences. 82, 5, p. 793-801 9 p.

Research output: Contribution to journalArticleScientificpeer-review

Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., 2016, 2016 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY. New York, NY: IEEE, p. 335-339 5 p. (IEEE International Symposium on Information Theory).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2015

Algebraic Methods in the Congested Clique

Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A. & Suomela, J., Jul 2015, PODC '15 : Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. New York: ACM, p. 143-152 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Subset Sum in the absence of concentration

Austrin, P., Kaski, P., Koivisto, M. K. H. & Nederlof, J., 2015, 32nd International Symposium on Theoretical Aspects of Computer: Science STACS’15, March 4–7, 2015, Garching, Germany . Mayr, E. W. & Ollinger, N. (eds.). Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 48-61 14 p. (Leibniz International Proceedings in Informatics; vol. 30).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
2014

Fast monotone summation over disjoint sets

Kaski, P., Koivisto, M., Korhonen, J. H. & Sergeev, I. S., May 2014, In : Information Processing Letters. 114, 5, p. 264-267 4 p.

Research output: Contribution to journalArticleScientificpeer-review

On the Number of Connected Sets in Bounded Degree Graphs

Kangas, K., Kaski, P., Koivisto, M. & Korhonen, J. H., 2014, Graph-Theoretic Concepts in Computer Science : 40th International Workshop, WG 2014 Nouan-le-Fuzelier, France, June 25–27, 2014 : Revised Selected Papers. Kratsch, D. & Todinca, I. (eds.). Cham: Springer International Publishing AG, p. 336-347 (Lecture Notes in Computer Science; vol. 8747).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2012

Fast Monotone Summation over Disjoint Sets

Kaski, P., Koivisto, M. & Korhonen, J. H., 2012, Parameterized and Exact Computation: 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings. Thilikos, D. & Woeginger, G. (eds.). Springer-Verlag, p. 159-170 12 p. (Lecture Notes in Computer Science; vol. 7535).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Fast zeta transforms for lattices with few irreducibles

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M., Nederlof, J. & Parviainen, P., 2012, SODA '12 Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, p. 1436-1444

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Finding Efficient Circuits for Ensemble Computation

Järvisalo, M., Kaski, P., Koivisto, M. & Korhonen, J. H., 2012, Theory and Applications of Satisfiability Testing – SAT 2012: 15th International Conference, Trento, Italy, June 17-20, 2012. Proceedings. Cimatti, A. & Sebastiani, R. (eds.). Springer-Verlag, p. 369-382 14 p. (Lecture Notes in Computer Science; vol. 7317).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Homomorphic Hashing for Sparse Coefficient Extraction

Kaski, P., Koivisto, M. & Nederlof, J., 2012, Parameterized and Exact Computation: 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings. Springer-Verlag, p. 147-158 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

The Traveling Salesman Problem in Bounded Degree Graphs

Bjorklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2012, In : ACM Transactions on Algorithms. 8, 2, p. Article Number: 18 13 p.

Research output: Contribution to journalArticleScientificpeer-review

2011

Local approximability of max-min and min-max linear programs

Floréen, P., Hassinen, M., Kaasinen, J., Kaski, P., Musto, T. & Suomela, J., 2011, In : Theory of Computing Systems. 49, 4, p. 672–697 26 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

The Cycle Switching Graph of the Steiner Triple Systems of Order 19 is Connected

Kaski, P., Mäkinen, V. & Östergård, P. R. J., 2011, In : Graphs and Combinatorics. 27, 4, p. 539-546 8 p.

Research output: Contribution to journalArticleScientificpeer-review

THE NUMBER OF LATIN SQUARES OF ORDER 11

Hulpke, A., Kaski, P. & Ostergard, P. R. J., 2011, In : Mathematics of Computation. 80, p. 1197-1219 23 p.

Research output: Contribution to journalArticleScientificpeer-review

2010

Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

Floréen, P., Kaski, P., Polishchuk, V. & Suomela, J., 2010, In : Algorithmica. 58, 1, p. 102-118 17 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Autumn temperature and carbon balance of a boreal Scots pine forest in Southern Finland

Vesala, T., Launiainen, S., Kolari, P., Pumpanen, J., Sevanto, S., Hari, P., Nikinmaa, E., Kaski, P., Mannila, H., Ukkonen, E., Piao, S. L. & Ciais, P., 2010, In : Biogeosciences. 7, 1, p. 163-176 14 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File

Brief Announcement: Distributed Almost Stable Marriage

Floréen, P., Kaski, P., Polishchuk, V. & Suomela, J., 2010, Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. New York: The Association for Computing Machinery, p. 281-282 2 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Covering and packing in linear space

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2010, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (Bordeaux, July 6--10, 2010) : Part I. USA: Springer-Verlag, p. 727-737 11 p. (Lecture Notes in Computer Science; vol. 6198).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Evaluation of permanents in rings and semirings

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2010, In : Information Processing Letters. 110, 20, p. 867-870 4 p.

Research output: Contribution to journalArticleScientificpeer-review

Exact cover via satisfiability: an empirical study

Junttila, T. & Kaski, P., 2010, Principles and Practice of Constraint Programming – CP 2010: 16th International Conference, CP 2010, St. Andrews, Scotland, September 6-10, 2010. Proceedings. Cohen, D. (ed.). Springer-Verlag, p. 297-304 8 p. (Lecture Notes in Computer Science; vol. 6308).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Properties of the Steiner Triple Systems of Order 19

Colbourn, C. J., Forbes, A. D., Grannell, M. J., Griggs, T. S., Kaski, P., Ostergard, P. R. J., Pike, D. A. & Pottonen, O., 10 Jul 2010, In : The Electronic Journal of Combinatorics. 17, 1, p. R98 30 p., 98.

Research output: Contribution to journalArticleScientificpeer-review

Testing the significance of patterns in data with cluster structure

Vuokko, N. & Kaski, P., 2010, (Accepted/In press) Proceedings of the 10th IEEE International Conference on Data Mining (ICDM2010, Sydney, December 14--17). IEEE Computer Society, p. to appear 6 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Trimmed Moebius Inversion and Graphs of Bounded Degree

Bjorklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2010, In : Theory of Computing Systems. 47, 3, p. 637-654 18 p.

Research output: Contribution to journalArticleScientificpeer-review

2009

A catalogue of the Steiner triple systems of order 19

Kaski, P., Östergård, P. R. J., Pottonen, O. & Kiviluoto, L., 2009, In : Bulletin of the Institute of Combinatorics and its Applications. 57, p. 35-41 7 p.

Research output: Contribution to journalArticleScientificpeer-review

An optimal local approximation algorithm for max-min linear programs

Floreen, P., Kaasinen, J., Kaski, P. & Suomela, J., 2009, SPAA’09: Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures. August 11–13, 2009. Calgary, Alberta, Canada. Meyer auf der Heide, F. & Bender, M. A. (eds.). ACM, p. 260-269 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File

Classification of resolvable balanced incomplete block designs: the unitals on 28 points

Kaski, P. & Östergård, P. R. J., 2009, In : Mathematica Slovaca. 59, p. 121-136 16 p.

Research output: Contribution to journalArticleScientificpeer-review

Counting paths and packings in Halves

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2009, Algorithms: ESA 2009 . Fiat, A. & Sanders, P. (eds.). Berlin, Heidelberg: Springer-Verlag, p. 578-586 9 p. (Lecture notes in computer science).

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

There are 1,132,835,421,602,062,347 nonisomorphic one-factorizations of K

Kaski, P. & Östergård, P. R. J., 2009, In : Journal of combinatorial designs.. 17, p. 147-159 13 p.

Research output: Contribution to journalArticleScientificpeer-review

2008

An enumeration of graphical designs

Chee, Y. M. & Kaski, P., 2008, In : Journal of combinatorial designs.. 16, p. 70-85 16 p.

Research output: Contribution to journalArticleScientificpeer-review

Approximating max-min linear programs with local algorithms

Floréen, P., Kaski, P., Musto, T. & Suomela, J., 2008, proceedings of the 2008 IEEE International Parallel and Distributed Processing Symposium, April 14-18, 2008, Miami, Florida: IEEE 2008. IEEE, 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Circumspect descent prevails in solving random constraint satisfaction problems

Alava, M., Ardelius, J., Aurell, E., Kaski, P., Krishnamurthy, S., Orponen, P. & Seitz, S., 7 Oct 2008, In : Proceedings of the National Academy of Sciences of the United States of America. 105, 40, p. 15253-15257 5 p.

Research output: Contribution to journalArticleScientificpeer-review

Computing the Tutte polynomial in vertex-exponential time

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2008, 49th Annual IEEE Symposium on Foundations of Computer Science. p. 677-686 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs

Kaski, P., Penttinen, A. & Suomela, J., 2008, In : Ad-Hoc & Sensor Wireless Networks. 6, 3-4, p. 239-263 25 p.

Research output: Contribution to journalArticleScientificpeer-review

libexact user's guide: version 1.0

Kaski, P. & Pottonen, O., 2008, Helsinki: Helsinki Institute for Information Technology HIIT. (HIIT technical reports; no. 2008-1)

Research output: Book/ReportBookScientificpeer-review

Local approximation algorithms for scheduling problems in sensor networks

Floréen, P., Kaski, P., Musto, T. & Suomela, J., 2008, Algorithmic Aspects of Wireless Sensor Networks: Third International Workshop, ALGOSENSORS 2007. Wrocław, Poland, July 14, 2007. Revised Selected Papers. Kutyłowski, M., Cichoń, J. & Kubiak, P. (eds.). Springer-Verlag, p. 99-113 15 p. (Lecture Notes in Computer Science; vol. 4837).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Steiner triple systems of order 19 and 21 with subsystems of order 7

Kaski, P., Östergård, P. R. J., Topalova, S. & Zlatarski, R., 2008, In : Discrete Mathematics. 308, 13, p. 2732-2741 10 p.

Research output: Contribution to journalArticleScientificpeer-review

There are exactly five biplanes with k = 11

Kaski, P. & Östergård, P. R. J., 2008, In : Journal of combinatorial designs.. 16, p. 117-127 11 p.

Research output: Contribution to journalArticleScientificpeer-review

The travelling salesman problem in bounded degree graphs

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2008, Automata, languages and programming. Berlin: Springer, p. 198-209 12 p.

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

Tight local approximation results for max-min linear programs

Floreen, P., Hassinen, M., Kaski, P. & Suomela, J., 2008, Algorithmic Aspects of Wireless Sensor Networks: Fourth International Workshop. ALGOSENSORS 2008. Reykjavik, Iceland, July 2008. Revised Selected Papers. Fekete, S. P. (ed.). Springer-Verlag, p. 2-17 16 p. (Lecture Notes in Computer Science; vol. 5389).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Trimmed moebius inversion and graphs of bounded degree

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2008, Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science. p. 85-96 12 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2007

A distributed approximation scheme for sleep scheduling in sensor networks

Floréen, P., Kaski, P. & Suomela, J., 2007, Sensor, Mesh and Ad Hoc Communications and Networks, 2007, SECON '07: IEEE 2007. IEEE, p. 152-161 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Coordinating concurrent transmissions: A constant-factor approximation of maximum-weight independent set in local conflict graphs

Kaski, P., Penttinen, A. & Suomela, J., 2007, Ad-Hoc, Mobile, and Wireless Networks: 6th International Conference, ADHOC-NOW 2007. Morelia, Mexico, September 24–26, 2007. Proceedings. Kranakis, E. & Opatrny, J. (eds.). Springer-Verlag, p. 74-86 13 p. (Lecture Notes in Computer Science; vol. 4686).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Engineering an efficient canonical labeling tool for large and sparse graphs

Junttila, T. & Kaski, P., 2007, Proceedings of the ninth Workshop on Algorithm Engineering and Experiments and the fourth Workshop on Analytic Algorithmics and Combinatorics. p. 135-149 15 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Fourier meets Möbius: fast subset convolution

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2007, STOC'07. p. 67-74 8 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

There exists no symmetric configuration with 33 points and line size 6

Kaski, P. & Östergård, P. R. J., 2007, In : Australasian Journal of Combinatorics. 38, p. 273-277 5 p.

Research output: Contribution to journalArticleScientificpeer-review