Editorial: Special Issue on International Workshop on Combinatorial Algorithms (IWOCA 2019)
- PDF / 113,038 Bytes
- 3 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 204 Views
Editorial: Special Issue on International Workshop on Combinatorial Algorithms (IWOCA 2019) Nadia Pisanti 1 & Charles Colbourn 2 & Roberto Grossi 1 Accepted: 16 October 2020/ # Springer Science+Business Media, LLC, part of Springer Nature 2020
This special issue contains eight articles which are based on extended abstracts presented at the 30th International Workshop on Combinatorial Algorithms (IWOCA), which was held at the University of Pisa, Italy, from 23 to 25 July, 2019. These extended abstracts were among the top papers presented at IWOCA 2019, and were selected with a very competitive peer-review process after which only 36 papers out of 73 submissions were accepted. Out of these 36, 11 were invited to this special issue, and 8 of them have been accepted for publication. Compared with the original conference submissions, the articles have been extended by full proofs and additional results, and have undergone a further rigorous reviewing process, following the TOCS standard. The eight articles are: 1. Matthias Bentert, Roman Haag, Christian Hofer, Tomohiro Koana, and André Nichterlein: Parameterized Complexity of Min-Power Asymmetric Connectivity. 2. Juho Lauri and Christodoulos Mitillos: Complexity of fall coloring for restricted graph classes. 3. Florian Stober and Armin Weiß: On the Average Case of MergeInsertion. 4. Arti Pandey, Michael A. Henning, and Vikash Tripathi: Complexity and Algorithms for Semipaired Domination in Graphs. 5. Zola Donovan, Vahan Mkrtchyan, and K. Subramani: Analyzing clustering and partitioning problems in selected VLSI models.
* Nadia Pisanti [email protected] Charles Colbourn [email protected] Roberto Grossi [email protected]
1
University of Pisa, Pisa, PI, Italy
2
Arizona State University, Tempe, AZ, USA
Theory of Computing Systems
6. Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda: Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings. 7. Yeganeh Bahoo, Prosenjit Bose, Stephane Durocher, and Thomas Shermer: Computing the k-visibility Region of a Point in a Polygon. 8. Aritra Banik, Ashwin Jacob, Vijay Kumar Paliwal, and Venkatesh Raman: Fixed Parameter Tractability of (n-k) List Coloring. The range of topics well illustrates the general scope of the IWOCA conference series, and this special issue on combinatorial algorithms especially highlights many combinatorial aspects related to graph theory, with a broad span of the discipline of combinatorial algorithms. First, Matthias Bentert, Roman Haag, Christian Hofer, Tomohiro Koana, and André Nichterlein in their paper “Parameterized Complexity of Min-Power Asymmetric Connectivity” investigate parameterized algorithms for the NP-hard problem MinPAC (Min-Power Asymmetric Connectivity) that has applications in wireless sensor networks. Juho Lauri and Christodoulos Mitillos, in their paper “Complexity of fall coloring for restricted graph classes”, show NP-completeness results for several versions of the problem of partitioning a g
Data Loading...
