LIPIcs, Volume 63
IPEC 2016, August 24-26, 2016, Aarhus, Denmark
Editors: Jiong Guo and Danny Hermelin
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Jianqi Zhou, Peihua Li, and Jiong Guo. Parameterized Approximation Algorithms for TSP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{zhou_et_al:LIPIcs.ISAAC.2022.50, author = {Zhou, Jianqi and Li, Peihua and Guo, Jiong}, title = {{Parameterized Approximation Algorithms for TSP}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {50:1--50:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.50}, URN = {urn:nbn:de:0030-drops-173358}, doi = {10.4230/LIPIcs.ISAAC.2022.50}, annote = {Keywords: FPT-approximation algorithms, the Traveling Salesman problem, the triangle inequality, fixed-parameter tractability, metric graphs} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Maël Dumas, Anthony Perez, and Ioan Todinca. A Cubic Vertex-Kernel for Trivially Perfect Editing. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dumas_et_al:LIPIcs.MFCS.2021.45, author = {Dumas, Ma\"{e}l and Perez, Anthony and Todinca, Ioan}, title = {{A Cubic Vertex-Kernel for Trivially Perfect Editing}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {45:1--45:14}, 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.45}, URN = {urn:nbn:de:0030-drops-144851}, doi = {10.4230/LIPIcs.MFCS.2021.45}, annote = {Keywords: Parameterized complexity, kernelization algorithms, graph modification, trivially perfect graphs} }
Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Haitao Jiang, Jiong Guo, Daming Zhu, and Binhai Zhu. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jiang_et_al:LIPIcs.CPM.2019.5, author = {Jiang, Haitao and Guo, Jiong and Zhu, Daming and Zhu, Binhai}, title = {{A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem}}, booktitle = {30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)}, pages = {5:1--5:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-103-0}, ISSN = {1868-8969}, year = {2019}, volume = {128}, editor = {Pisanti, Nadia and P. Pissis, Solon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.5}, URN = {urn:nbn:de:0030-drops-104769}, doi = {10.4230/LIPIcs.CPM.2019.5}, annote = {Keywords: Maximal strip recovery, complementary maximal strip recovery, computational genomics, approximation algorithm, local search} }
Published in: LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Shu Zhang, Daming Zhu, Haitao Jiang, Jingjing Ma, Jiong Guo, and Haodi Feng. Can a permutation be sorted by best short swaps?. In 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 105, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{zhang_et_al:LIPIcs.CPM.2018.14, author = {Zhang, Shu and Zhu, Daming and Jiang, Haitao and Ma, Jingjing and Guo, Jiong and Feng, Haodi}, title = {{Can a permutation be sorted by best short swaps?}}, booktitle = {29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018)}, pages = {14:1--14:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-074-3}, ISSN = {1868-8969}, year = {2018}, volume = {105}, editor = {Navarro, Gonzalo and Sankoff, David and Zhu, Binhai}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.14}, URN = {urn:nbn:de:0030-drops-86957}, doi = {10.4230/LIPIcs.CPM.2018.14}, annote = {Keywords: Algorithm, Complexity, Short Swap, Permutation, Reversal} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Proceedings{guo_et_al:LIPIcs.IPEC.2016, title = {{LIPIcs, Volume 63, IPEC'16, Complete Volume}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, 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}, URN = {urn:nbn:de:0030-drops-69572}, doi = {10.4230/LIPIcs.IPEC.2016}, annote = {Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Discrete Mathematics} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{guo_et_al:LIPIcs.IPEC.2016.0, author = {Guo, Jiong and Hermelin, Danny}, title = {{Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {0:i--0:xiv}, 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.0}, URN = {urn:nbn:de:0030-drops-69180}, doi = {10.4230/LIPIcs.IPEC.2016.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors} }
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 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Akanksha Agrawal, Sushmita Gupta, Saket Saurabh, and Roohani Sharma. Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{agrawal_et_al:LIPIcs.IPEC.2016.2, author = {Agrawal, Akanksha and Gupta, Sushmita and Saurabh, Saket and Sharma, Roohani}, title = {{Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {2:1--2:14}, 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.2}, URN = {urn:nbn:de:0030-drops-69400}, doi = {10.4230/LIPIcs.IPEC.2016.2}, annote = {Keywords: independent feedback vertex set, fixed parameter tractable, exact algorithm, enumeration} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bacso_et_al:LIPIcs.IPEC.2016.3, author = {Bacs\'{o}, G\'{a}bor and Marx, D\'{a}niel and Tuza, Zsolt}, title = {{H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {3:1--3:12}, 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.3}, URN = {urn:nbn:de:0030-drops-69397}, doi = {10.4230/LIPIcs.IPEC.2016.3}, annote = {Keywords: independent set, scattered set, subexponential algorithms, H-free graphs} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Max Bannach and Till Tantau. Parallel Multivariate Meta-Theorems. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bannach_et_al:LIPIcs.IPEC.2016.4, author = {Bannach, Max and Tantau, Till}, title = {{Parallel Multivariate Meta-Theorems}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {4:1--4:17}, 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.4}, URN = {urn:nbn:de:0030-drops-69227}, doi = {10.4230/LIPIcs.IPEC.2016.4}, annote = {Keywords: Parallel computation, FPT, meta-theorems, tree width, tree depth} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5, author = {van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej}, title = {{Finding Secluded Places of Special Interest in Graphs}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {5:1--5:16}, 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.5}, URN = {urn:nbn:de:0030-drops-69380}, doi = {10.4230/LIPIcs.IPEC.2016.5}, annote = {Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Parameterized Complexity of Dependency Detection in Relational Databases. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blasius_et_al:LIPIcs.IPEC.2016.6, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin}, title = {{The Parameterized Complexity of Dependency Detection in Relational Databases}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {6:1--6:13}, 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.6}, URN = {urn:nbn:de:0030-drops-69202}, doi = {10.4230/LIPIcs.IPEC.2016.6}, annote = {Keywords: parameterized complexity, unique column combination, functional dependency, inclusion dependency, profiling relational data} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A Faster Parameterized Algorithm for Pseudoforest Deletion. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2016.7, author = {Bodlaender, Hans L. and Ono, Hirotaka and Otachi, Yota}, title = {{A Faster Parameterized Algorithm for Pseudoforest Deletion}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {7:1--7:12}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.7}, URN = {urn:nbn:de:0030-drops-69246}, doi = {10.4230/LIPIcs.IPEC.2016.7}, annote = {Keywords: pseudoforest deletion, graph class, width parameter, parameterized complexity} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Glencora Borradaile and Hung Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{borradaile_et_al:LIPIcs.IPEC.2016.8, author = {Borradaile, Glencora and Le, Hung}, title = {{Optimal Dynamic Program for r-Domination Problems over Tree Decompositions}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {8:1--8:23}, 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.8}, URN = {urn:nbn:de:0030-drops-69199}, doi = {10.4230/LIPIcs.IPEC.2016.8}, annote = {Keywords: r-dominating set, Exponential Time Hypothesis, Dynamic Programming} }
Feedback for Dagstuhl Publishing