LIPIcs, Volume 148
IPEC 2019, September 11-13, 2019, Munich, Germany
Editors: Bart M. P. Jansen and Jan Arne Telle
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Classes of Intersection Digraphs with Good Algorithmic Properties. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{jaffke_et_al:LIPIcs.STACS.2022.38, author = {Jaffke, Lars and Kwon, O-joung and Telle, Jan Arne}, title = {{Classes of Intersection Digraphs with Good Algorithmic Properties}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {38:1--38:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.38}, URN = {urn:nbn:de:0030-drops-158480}, doi = {10.4230/LIPIcs.STACS.2022.38}, annote = {Keywords: intersection digraphs, H-digraphs, reflexive digraphs, directed domination, directed H-homomorphism} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Svein Høgemo, Christophe Paul, and Jan Arne Telle. Hierarchical Clusterings of Unweighted Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hgemo_et_al:LIPIcs.MFCS.2020.47, author = {H{\o}gemo, Svein and Paul, Christophe and Telle, Jan Arne}, title = {{Hierarchical Clusterings of Unweighted Graphs}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {47:1--47:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.47}, URN = {urn:nbn:de:0030-drops-127139}, doi = {10.4230/LIPIcs.MFCS.2020.47}, annote = {Keywords: Hierarchical Clustering} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Hans L. Bodlaender, Lars Jaffke, and Jan Arne Telle. Typical Sequences Revisited - Computing Width Parameters of Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bodlaender_et_al:LIPIcs.STACS.2020.57, author = {Bodlaender, Hans L. and Jaffke, Lars and Telle, Jan Arne}, title = {{Typical Sequences Revisited - Computing Width Parameters of Graphs}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {57:1--57:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.57}, URN = {urn:nbn:de:0030-drops-119189}, doi = {10.4230/LIPIcs.STACS.2020.57}, annote = {Keywords: typical sequences, treewidth, series parallel digraphs, cutwidth, modified cutwidth} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{jansen_et_al:LIPIcs.IPEC.2019, title = {{LIPIcs, Volume 148, IPEC'19, Complete Volume}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019}, URN = {urn:nbn:de:0030-drops-116409}, doi = {10.4230/LIPIcs.IPEC.2019}, annote = {Keywords: Theory of computation, Parameterized complexity and exact algorithms} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jansen_et_al:LIPIcs.IPEC.2019.0, author = {Jansen, Bart M. P. and Telle, Jan Arne}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.0}, URN = {urn:nbn:de:0030-drops-114618}, doi = {10.4230/LIPIcs.IPEC.2019.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and Counting Permutations via CSPs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{berendsohn_et_al:LIPIcs.IPEC.2019.1, author = {Berendsohn, Benjamin Aram and Kozma, L\'{a}szl\'{o} and Marx, D\'{a}niel}, title = {{Finding and Counting Permutations via CSPs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.1}, URN = {urn:nbn:de:0030-drops-114627}, doi = {10.4230/LIPIcs.IPEC.2019.1}, annote = {Keywords: permutations, pattern matching, constraint satisfaction, exponential time} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro, Fábio Protti, and Uéverton S. Souza. Width Parameterizations for Knot-Free Vertex Deletion on Digraphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bessy_et_al:LIPIcs.IPEC.2019.2, author = {Bessy, St\'{e}phane and Bougeret, Marin and Carneiro, Alan D. A. and Protti, F\'{a}bio and Souza, U\'{e}verton S.}, title = {{Width Parameterizations for Knot-Free Vertex Deletion on Digraphs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {2:1--2:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.2}, URN = {urn:nbn:de:0030-drops-114631}, doi = {10.4230/LIPIcs.IPEC.2019.2}, annote = {Keywords: Knot, deadlock, width measure, FPT, W\lbrack1\rbrack-hard, directed feedback vertex set} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Markus Bläser and Christian Engels. Parameterized Valiant’s Classes. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blaser_et_al:LIPIcs.IPEC.2019.3, author = {Bl\"{a}ser, Markus and Engels, Christian}, title = {{Parameterized Valiant’s Classes}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.3}, URN = {urn:nbn:de:0030-drops-114648}, doi = {10.4230/LIPIcs.IPEC.2019.3}, annote = {Keywords: Algebraic complexity theory, parameterized complexity theory, Valiant’s classes} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Johannes Blum. Hierarchy of Transportation Network Parameters and Hardness Results. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blum:LIPIcs.IPEC.2019.4, author = {Blum, Johannes}, title = {{Hierarchy of Transportation Network Parameters and Hardness Results}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {4:1--4:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.4}, URN = {urn:nbn:de:0030-drops-114656}, doi = {10.4230/LIPIcs.IPEC.2019.4}, annote = {Keywords: Graph Parameters, Skeleton Dimension, Highway Dimension, k-Center} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Édouard Bonnet and Nidhi Purohit. Metric Dimension Parameterized by Treewidth. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bonnet_et_al:LIPIcs.IPEC.2019.5, author = {Bonnet, \'{E}douard and Purohit, Nidhi}, title = {{Metric Dimension Parameterized by Treewidth}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.5}, URN = {urn:nbn:de:0030-drops-114668}, doi = {10.4230/LIPIcs.IPEC.2019.5}, annote = {Keywords: Metric Dimension, Treewidth, Parameterized Hardness} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Marco Bressan. Faster Subgraph Counting in Sparse Graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bressan:LIPIcs.IPEC.2019.6, author = {Bressan, Marco}, title = {{Faster Subgraph Counting in Sparse Graphs}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {6:1--6:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.6}, URN = {urn:nbn:de:0030-drops-114673}, doi = {10.4230/LIPIcs.IPEC.2019.6}, annote = {Keywords: subgraph counting, tree decomposition, degeneracy} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Rajesh Chitnis and Graham Cormode. Towards a Theory of Parameterized Streaming Algorithms. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chitnis_et_al:LIPIcs.IPEC.2019.7, author = {Chitnis, Rajesh and Cormode, Graham}, title = {{Towards a Theory of Parameterized Streaming Algorithms}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {7:1--7:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.7}, URN = {urn:nbn:de:0030-drops-114682}, doi = {10.4230/LIPIcs.IPEC.2019.7}, annote = {Keywords: Parameterized Algorithms, Streaming Algorithms, Kernels} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Rajesh Chitnis and Andreas Emil Feldmann. FPT Inapproximability of Directed Cut and Connectivity Problems. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chitnis_et_al:LIPIcs.IPEC.2019.8, author = {Chitnis, Rajesh and Feldmann, Andreas Emil}, title = {{FPT Inapproximability of Directed Cut and Connectivity Problems}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.8}, URN = {urn:nbn:de:0030-drops-114692}, doi = {10.4230/LIPIcs.IPEC.2019.8}, annote = {Keywords: Directed graphs, cuts, connectivity, Steiner problems, FPT inapproximability} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, and Siddharth Gupta. C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dalozzo_et_al:LIPIcs.IPEC.2019.9, author = {Da Lozzo, Giordano and Eppstein, David and Goodrich, Michael T. and Gupta, Siddharth}, title = {{C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {9:1--9:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.9}, URN = {urn:nbn:de:0030-drops-114705}, doi = {10.4230/LIPIcs.IPEC.2019.9}, annote = {Keywords: Clustered planarity, carving-width, non-crossing partitions, FPT} }
Feedback for Dagstuhl Publishing