Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Samir Datta and Kishlaya Jaiswal. Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{datta_et_al:LIPIcs.MFCS.2021.36, author = {Datta, Samir and Jaiswal, Kishlaya}, title = {{Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {36:1--36:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.36}, URN = {urn:nbn:de:0030-drops-144763}, doi = {10.4230/LIPIcs.MFCS.2021.36}, annote = {Keywords: permanent mod powers of 2, parallel computation, graphs, shortest disjoint paths, shortest disjoint cycles} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Andreas Björklund and Petteri Kaski. Counting Short Vector Pairs by Inner Product and Relations to the Permanent. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2021.29, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri}, title = {{Counting Short Vector Pairs by Inner Product and Relations to the Permanent}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {29:1--29:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.29}, URN = {urn:nbn:de:0030-drops-140988}, doi = {10.4230/LIPIcs.ICALP.2021.29}, annote = {Keywords: additive reconstruction, Chinese Remainder Theorem, counting, inner product, modular tomography, orthogonal vectors, permanent} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Andreas Björklund. An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bjorklund:LIPIcs.STACS.2021.15, author = {Bj\"{o}rklund, Andreas}, title = {{An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {15:1--15:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.15}, URN = {urn:nbn:de:0030-drops-136601}, doi = {10.4230/LIPIcs.STACS.2021.15}, annote = {Keywords: Hamiltonian cycle, directed graph, worst case analysis algorithm} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Approximate Counting of k-Paths: Deterministic and in Polynomial Space. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2019.24, author = {Bj\"{o}rklund, Andreas and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav}, title = {{Approximate Counting of k-Paths: Deterministic and in Polynomial Space}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.24}, URN = {urn:nbn:de:0030-drops-106001}, doi = {10.4230/LIPIcs.ICALP.2019.24}, annote = {Keywords: parameterized complexity, approximate counting, \{ k\}-Path} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Andreas Björklund and Ryan Williams. Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2019.25, author = {Bj\"{o}rklund, Andreas and Williams, Ryan}, title = {{Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar Vectors}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.25}, URN = {urn:nbn:de:0030-drops-106018}, doi = {10.4230/LIPIcs.ICALP.2019.25}, annote = {Keywords: permanent, Hamiltonian cycle, orthogonal vectors} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Andreas Björklund, Petteri Kaski, and Ryan Williams. Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2019.26, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Williams, Ryan}, title = {{Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {26:1--26:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.26}, URN = {urn:nbn:de:0030-drops-106023}, doi = {10.4230/LIPIcs.ICALP.2019.26}, annote = {Keywords: equation systems, polynomial method} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Andreas Björklund. Exploiting Sparsity for Bipartite Hamiltonicity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bjorklund:LIPIcs.ISAAC.2018.3, author = {Bj\"{o}rklund, Andreas}, title = {{Exploiting Sparsity for Bipartite Hamiltonicity}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {3:1--3:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.3}, URN = {urn:nbn:de:0030-drops-99510}, doi = {10.4230/LIPIcs.ISAAC.2018.3}, annote = {Keywords: Hamiltonian cycle, bipartite graph} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Connected Subgraphs with Maximum-Degree-Aware Sieving. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bjorklund_et_al:LIPIcs.ISAAC.2018.17, author = {Bj\"{o}rklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko}, title = {{Counting Connected Subgraphs with Maximum-Degree-Aware Sieving}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {17:1--17:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.17}, URN = {urn:nbn:de:0030-drops-99655}, doi = {10.4230/LIPIcs.ISAAC.2018.17}, annote = {Keywords: graph embedding, k-path, subgraph counting, maximum degree} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Andreas Björklund and Thore Husfeldt. Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bjorklund_et_al:LIPIcs.ISAAC.2018.19, author = {Bj\"{o}rklund, Andreas and Husfeldt, Thore}, title = {{Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {19:1--19:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.19}, URN = {urn:nbn:de:0030-drops-99670}, doi = {10.4230/LIPIcs.ISAAC.2018.19}, annote = {Keywords: Shortest disjoint paths, Cubic planar graph} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Andreas Björklund, Petteri Kaski, and Ryan Williams. Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bjorklund_et_al:LIPIcs.IPEC.2017.6, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Williams, Ryan}, title = {{Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.6}, URN = {urn:nbn:de:0030-drops-85728}, doi = {10.4230/LIPIcs.IPEC.2017.6}, annote = {Keywords: Besicovitch set, fermionant, finite field, finite vector space, Hamiltonian cycle, homogeneous polynomial, Kakeya set, permanent, polynomial evaluatio} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 91:1-91:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2017.91, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Koutis, Ioannis}, title = {{Directed Hamiltonicity and Out-Branchings via Generalized Laplacians}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {91:1--91:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.91}, URN = {urn:nbn:de:0030-drops-74208}, doi = {10.4230/LIPIcs.ICALP.2017.91}, annote = {Keywords: counting, directed Hamiltonicity, graph Laplacian, independent set, k-internal out-branching} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Andreas Björklund. Determinant Sums for Hamiltonicity (Invited Talk). In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bjorklund:LIPIcs.IPEC.2016.1, author = {Bj\"{o}rklund, Andreas}, title = {{Determinant Sums for Hamiltonicity}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.1}, URN = {urn:nbn:de:0030-drops-69485}, doi = {10.4230/LIPIcs.IPEC.2016.1}, annote = {Keywords: Hamiltonian cycle, exact algorithms, matrix determinant, algebraic techniques} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Andreas Björklund. Coloring Graphs Having Few Colorings Over Path Decompositions. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 13:1-13:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bjorklund:LIPIcs.SWAT.2016.13, author = {Bj\"{o}rklund, Andreas}, title = {{Coloring Graphs Having Few Colorings Over Path Decompositions}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {13:1--13:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.13}, URN = {urn:nbn:de:0030-drops-60353}, doi = {10.4230/LIPIcs.SWAT.2016.13}, annote = {Keywords: Graph vertex coloring, path decomposition, Alon-Tarsi theorem} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Andreas Björklund. Below All Subsets for Some Permutational Counting Problems. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bjorklund:LIPIcs.SWAT.2016.17, author = {Bj\"{o}rklund, Andreas}, title = {{Below All Subsets for Some Permutational Counting Problems}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {17:1--17:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.17}, URN = {urn:nbn:de:0030-drops-60399}, doi = {10.4230/LIPIcs.SWAT.2016.17}, annote = {Keywords: Matrix Permanent, Hamiltonian Cycles, Asymmetric TSP} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Probably Optimal Graph Motifs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 20-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{bjorklund_et_al:LIPIcs.STACS.2013.20, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}, title = {{Probably Optimal Graph Motifs}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {20--31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.20}, URN = {urn:nbn:de:0030-drops-39196}, doi = {10.4230/LIPIcs.STACS.2013.20}, annote = {Keywords: graph motif, FPT algorithm} }
Feedback for Dagstuhl Publishing