LIPIcs, Volume 123
ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan
Editors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Proceedings{hsu_et_al:LIPIcs.ISAAC.2018, title = {{LIPIcs, Volume 123, ISAAC'18, Complete Volume}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2019}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018}, URN = {urn:nbn:de:0030-drops-101600}, doi = {10.4230/LIPIcs.ISAAC.2018}, annote = {Keywords: Mathematics of computing, Theory of computation, Data structures design and analysis, Computing methodologies} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hsu_et_al:LIPIcs.ISAAC.2018.0, author = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {0:i--0:xviii}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.0}, URN = {urn:nbn:de:0030-drops-99488}, doi = {10.4230/LIPIcs.ISAAC.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Shang-Hua Teng. Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk). In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{teng:LIPIcs.ISAAC.2018.1, author = {Teng, Shang-Hua}, title = {{Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {1:1--1:1}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.1}, URN = {urn:nbn:de:0030-drops-99495}, doi = {10.4230/LIPIcs.ISAAC.2018.1}, annote = {Keywords: scalable algorithms, axiomatization, graph sparsification, local algorithms, advanced sampling, big data, network sciences, machine learning, social influence, beyond graph theory} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Clifford Stein. Approximate Matchings in Massive Graphs via Local Structure (Invited Talk). In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{stein:LIPIcs.ISAAC.2018.2, author = {Stein, Clifford}, title = {{Approximate Matchings in Massive Graphs via Local Structure}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {2:1--2:1}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.2}, URN = {urn:nbn:de:0030-drops-99505}, doi = {10.4230/LIPIcs.ISAAC.2018.2}, annote = {Keywords: matching, dynamic algorithms, parallel algorithms, approximation algorithms} }
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.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)
Ahad N. Zehmakan. Opinion Forming in Erdös-Rényi Random Graph and Expanders. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{n.zehmakan:LIPIcs.ISAAC.2018.4, author = {N. Zehmakan, Ahad}, title = {{Opinion Forming in Erd\"{o}s-R\'{e}nyi Random Graph and Expanders}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {4:1--4: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.4}, URN = {urn:nbn:de:0030-drops-99529}, doi = {10.4230/LIPIcs.ISAAC.2018.4}, annote = {Keywords: majority model, random graph, expander graphs, dynamic monopoly, bootstrap percolation} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, and Veronika Slívová. Colouring (P_r+P_s)-Free Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{klimosova_et_al:LIPIcs.ISAAC.2018.5, author = {Klimosov\'{a}, Tereza and Mal{\'\i}k, Josef and Masar{\'\i}k, Tom\'{a}s and Novotn\'{a}, Jana and Paulusma, Dani\"{e}l and Sl{\'\i}vov\'{a}, Veronika}, title = {{Colouring (P\underliner+P\underlines)-Free Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {5:1--5: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.5}, URN = {urn:nbn:de:0030-drops-99533}, doi = {10.4230/LIPIcs.ISAAC.2018.5}, annote = {Keywords: vertex colouring, H-free graph, linear forest} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Guillaume Ducoffe and Alexandru Popa. The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ducoffe_et_al:LIPIcs.ISAAC.2018.6, author = {Ducoffe, Guillaume and Popa, Alexandru}, title = {{The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {6:1--6: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.6}, URN = {urn:nbn:de:0030-drops-99549}, doi = {10.4230/LIPIcs.ISAAC.2018.6}, annote = {Keywords: maximum matching, FPT in P, modular decomposition, pruned graphs, one-vertex extensions, P\underline4-structure} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Davide Bilò and Kleitos Papadopoulos. A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bilo_et_al:LIPIcs.ISAAC.2018.7, author = {Bil\`{o}, Davide and Papadopoulos, Kleitos}, title = {{A Novel Algorithm for the All-Best-Swap-Edge Problem on Tree Spanners}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {7:1--7: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.7}, URN = {urn:nbn:de:0030-drops-99557}, doi = {10.4230/LIPIcs.ISAAC.2018.7}, annote = {Keywords: Transient edge failure, best swap edges, tree spanner} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient Enumeration of Dominating Sets for Sparse Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kurita_et_al:LIPIcs.ISAAC.2018.8, author = {Kurita, Kazuhiro and Wasa, Kunihiro and Arimura, Hiroki and Uno, Takeaki}, title = {{Efficient Enumeration of Dominating Sets for Sparse Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.8}, URN = {urn:nbn:de:0030-drops-99560}, doi = {10.4230/LIPIcs.ISAAC.2018.8}, annote = {Keywords: Enumeration algorithm, polynomial amortized time, dominating set, girth, degeneracy} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{rahman_et_al:LIPIcs.ISAAC.2018.9, author = {Rahman, Md Lutfar and Watson, Thomas}, title = {{Complexity of Unordered CNF Games}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {9:1--9: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.9}, URN = {urn:nbn:de:0030-drops-99574}, doi = {10.4230/LIPIcs.ISAAC.2018.9}, annote = {Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, and Alexander V. Smal. Half-Duplex Communication Complexity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hoover_et_al:LIPIcs.ISAAC.2018.10, author = {Hoover, Kenneth and Impagliazzo, Russell and Mihajlin, Ivan and Smal, Alexander V.}, title = {{Half-Duplex Communication Complexity}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {10:1--10: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.10}, URN = {urn:nbn:de:0030-drops-99583}, doi = {10.4230/LIPIcs.ISAAC.2018.10}, annote = {Keywords: communication complexity, half-duplex channel, information theory} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Takashi Ishizuka and Naoyuki Kamiyama. On the Complexity of Stable Fractional Hypergraph Matching. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ishizuka_et_al:LIPIcs.ISAAC.2018.11, author = {Ishizuka, Takashi and Kamiyama, Naoyuki}, title = {{On the Complexity of Stable Fractional Hypergraph Matching}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {11:1--11: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.11}, URN = {urn:nbn:de:0030-drops-99590}, doi = {10.4230/LIPIcs.ISAAC.2018.11}, annote = {Keywords: fractional hypergraph matching, stable matching, PPAD-completeness} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Matthew P. Johnson. Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{johnson:LIPIcs.ISAAC.2018.12, author = {Johnson, Matthew P.}, title = {{Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {12:1--12: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.12}, URN = {urn:nbn:de:0030-drops-99600}, doi = {10.4230/LIPIcs.ISAAC.2018.12}, annote = {Keywords: phylogenetic trees, rooted triple entailment, NP-Completeness, directed hypergraphs, acyclic induced subgraphs, computational complexity} }
Feedback for Dagstuhl Publishing