30th International Workshop on
Combinatorial Algorithms
IWOCA 2019, Pisa, 23-25 July
Workshop supported by the University of Pisa
Related events: CPM 2019, StringMasters, GraphMasters
Aims and Scope
The series of IWOCA conferences grew out of almost 30 years history of the International (since 2007) respectively Australasian (until 2006) Workshops on Combinatorial Algorithms. Previous IWOCA and AWOCA meetings have been held in Australia, Canada, Czech Republic, Finland, France, Indonesia, India, Italy, Japan, Singapore, South Korea, UK, and USA. Previous IWOCAs can be found at http://www.iwoca.org/
We solicit high-quality papers in the broad area of combinatorial algorithms. The topics include (but are not restricted to):
- Algorithms and Data Structures
- Complexity Theory
- Graph Theory & Combinatorics
- Combinatorial Optimization
- Cryptography & Information Security
- Algorithms on Strings & Graphs
- Graph Drawing & Labelling
- Computational Algebra & Geometry
- Computational Biology
- Algorithms for Big Data and Networks Analytics
- Probabilistic & Randomised Algorithms
- New Paradigms of Computation
Programme
Tuesday, July 23
8:30-8:50 | Welcome and registration |
8:50-9:00 | Opening |
9:00-10:00 | Invited Lecture by Marinella Sciortino (Università di Palermo) BWT Variants: A Combinatorial Investigation |
Session 1 (Chair: Rossano Venturini) | |
10:00-10:25 | Simone Rinaldi, Srecko Brlek, Andrea Frosini, Elisa Pergola, Ilaria Mancini. Burrows-Wheeler transform of words defined by morphisms |
10:25-10:50 | Florian Stober, Armin Weiss. On the Average Case of MergeInsertion |
10:50-11:15 | Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. Shortest Unique Palindromic Substring Queries on Run-Length Encoded Strings |
11:15-11:35 | Coffee Break |
Session 2 (Chair: Lucia D. Penso) | |
11:35-12:00 | Herman Haverkort, David Kübel, Elmar Langetepe. Shortest-Path-Preserving Rounding |
12:00-12:25 | Mehdi Khosravian Ghadikolaei, Nikolaos Melissinos, Jerome Monnot, Aris Pagourtzis. Extension and its price for the connected vertex cover problem |
12:25-12:50 | Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura. An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Sparse Graphs |
12:50-13:15 | Juho Lauri, Christodoulos Mitillos. Complexity of fall coloring for restricted graph classes |
13:15-14:30 | Lunch Break |
Session 3 (Chair: Dalibor Froncek) | |
14:30-14:55 | Pierre Cazals, Darties, Benoit Chateau, Rodolphe Giroudeau, Mathias Weller. Power Edge Set and Zero Forcing Set remain difficult in cubic graphs |
14:55-15:20 | Zola Donovan, K. Subramani, Vahan Mkrtchyan. Disjoint clustering in combinatorial circuits |
15:20-15:45 | Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki. An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number |
15:45-16:00 | Coffee Break |
Session 4 (Chair: Marinella Sciortino) | |
16:00-16:25 | Janka Chlebikova, Clément Dallard. Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs |
16:25-16:50 | Giordano Da Lozzo, Ignaz Rutter. Reaching 3-Connectivity via Edge-edge Additions |
16:50-17:15 | Dalibor Froncek, Jiangyi Qiu. Supermagic graphs with many odd degrees |
** Special session ** | |
17:15-17:30 | IWOCA Steering Committee. Business meeting |
17:30-18:30 | Gabriele Fici, Dalibor Froncek. Presentation of collected open problems |
Wednesday, July 24
9:00-10:00 | Invited Lecture by Ugo Vaccaro (Università di Salerno) Superimposed Codes and their Applications: Old Results in New Light |
Session 5 (Chair: Charles Colbourn) | |
10:00-10:25 | Yeganeh Bahoo, Prosenjit Bose, Stephane Durocher, Thomas Shermer. Computing the k-Crossing Visibility Region of a Point in a Polygon |
10:25-10:50 | Mirza Galib Anwarul Husain Baig, Deepanjan Kesh, Chirag Sodani. An Improved Scheme in the Two Query Adaptive Bitprobe Model |
10:50-11:15 | Martin Balko, Sujoy Bhore, Leonardo Martínez-Sandoval, Pavel Valtr. On Erd\H{o}s–Szekeres-type problems for $k$-convex point sets |
11:15-11:35 | Coffee Break |
Session 6 (Chair: Ugo Vaccaro) | |
11:35-12:00 | Prajeesh Appattu Vallapil, Paramasivam Krishnan, Kamatchi Nainarraj. A note on handicap incomplete tournaments |
12:00-12:25 | Gennaro Cordasco, Luisa Gargano, Adele Rescigno. Dual Domination |
12:25-12:50 | Arindam Biswas, Venkatesh Raman, Saket Saurabh. Solving Group Interval Scheduling Efficently |
12:50-13:15 | Fumito Miyake, Eiji Takimoto, Kohei Hatano. Succinct Representation of Linear Extensions via MDDs and Its Application to Scheduling under Precedence Constraints |
13:15-14:20 | Lunch Break |
Session 7 (Chair: Ian Wanless) | |
14:20-14:45 | Alessio Conte, Mamadou Moustapha Kanté, Andrea Marino, Takeaki Uno. Maximal irredundant set enumeration in bounded-degeneracy and bounded-degree hypergraphs |
14:45-15:10 | Rahul Raj Gupta, Sushanta Karmakar. Incremental algorithm for minimum cut and edge connectivity in hypergraph |
15:10-15:35 | Michel Habib, Fabien de Montgolfier, Lalla Mouatadid, Mengchuan Zou. A General Algorithmic Scheme for Modular Decompositions of Hypergraphs and Applications |
15:35-16:00 | Lachlan Plant, Lucia Moura. Maximum clique exhaustive search in circulant k-hypergraphs |
Social Trip and Dinner | |
16:00 | Departure from Pisa. Meeting point at the conference venue, bus with seaside excursion and dinner at Livorno |
Thursday, July 25
9:00-10:00 | Invited Lecture by Stéphane Vialette (Université Paris-Est Marne-la-Vallée) On Square Permutations |
Session 8 (Chair: Jackie Daykin) | |
10:00-10:25 | Magsarjav Bataa, Kunsoo Park, Amihood Amir, Gad M Landau, Sung Gwan Park. Finding Periods in Cartesian Tree Matching |
10:25-10:50 | Hans-Joachim Boeckenhauer, Nina Corvelo Benz, Dennis Komm. Call Admission on Trees with Advice (Extended Abstract) |
10:50-11:15 | Jesper Jansson, Konstantinos Mampentzidis, Ramesh Rajaby, Wing-Kin Sung. Computing the Rooted Triplet Distance between Phylogenetic Networks |
11:15-11:35 | Coffee Break |
Session 9 (Chair: Stéphane Vialette) | |
11:35-12:00 | Anjeneya Swami Kare, I. Vinod Reddy. Parameterized Algorithms for Graph Burning Problem |
12:00-12:25 | Sandip Banerjee, Sujoy Bhore. Algorithms and Hardness results on Liar’s Dominating Set and $k$-tuple Dominating Set |
12:25-12:50 | Aritra Banik, Ashwin Jacob, Vijay Kumar Paliwal, Venkatesh Raman. Fixed-parameter tractability of (n-k) List Coloring |
12:50-13:15 | Matthias Bentert, Roman Haag, Christian Hofer, Tomohiro Koana, André Nichterlein. Parameterized Complexity of Min-Power Asymmetric Connectivity |
13:15-14:30 | Lunch Break |
Session 10 (Chair: Lucia Moura) | |
14:30-14:55 | Mitre C. Dourado, Lucia D. Penso, Dieter Rautenbach. The hull number in the convexity of induced paths of order 3 |
14:55-15:20 | Michael A Henning, Arti Pandey, Vikash Tripathi. Complexity and Algorithms for Semipaired Domination in Graphs |
15:20-15:45 | Suthee Ruangwises, Toshiya Itoh. Stable Noncrossing Matchings |
15:45-16:00 | Coffee Break |
Session 11 (Chair: Andrea Marino) | |
16:00-16:25 | Sandip Das, Harmender Gahlawat, Uma Kant Sahoo, Sagnik Sen. Cops and robber on some families of oriented graphs |
16:25-16:50 | Yuan Xue, Boting Yang, Farong Zhong, Sandra Zilles. A Partition Approach to Lower Bounds for Zero-Visibility Cops and Robber |
17:00 | Farewell |
Program Committee
Hiroki Arimura (Hokkaido University, Japan)
Hideo Bannai (Kyushu University, Japan)
Philip Bille (Technical University of Denmark)
Paola Bonizzoni (University of Milano Bicocca, Italy)
Gerth Stolting Brodal (Aarhus University, Denmark)
Maria Chudnovsky (Princeton University, USA)
Charles Colbourn (co-chair, Arizona State University, USA)
Dalibor Froncek (University of Minnesota - Duluth, USA)
Travis Gagie (Diego Portales University, Chile)
Serge Gaspers (UNSW Sydney and Data61, CSIRO, Australia)
Dora Giammarresi (University of Roma Tor Vergata, Italy)
Roberto Grossi (co-chair, University of Pisa, Italy)
Jan Holub (Czech Technical University in Prague, Czech Republic)
Costas Iliopoulos (King’s College London, UK)
Artur Jez (University of Wroclaw, Poland)
Gregory Kucherov (CNRS & University of Paris Est, France)
Gad Landau (University of Haifa, Israel)
Thierry Lecroq (University of Rouen, France)
Christos Makris (University of Patras, Greece)
Sebastian Maneth (University of Bremen)
Sabrina Mantaci (University of Palermo, Italy)
Lucia Moura (University of Ottawa, Canada)
Patric R. J. Östergård (Aalto University, Finland)
Kunsoo Park (Seoul National University, South Korea)
David Pike (Memorial University of Newfoundland, Canada)
Nadia Pisanti (co-chair, University of Pisa, Italy)
Solon Pissis (CWI Amsterdam, the Netherlands)
Alexandru Popa (University of Bucharest, Romania)
Rajeev Raman (University of Leicester, UK)
Frank Ruskey (University of Victoria, Canada)
Marinella Sciortino (University of Palermo, Italy)
Rahul Shah (Louisiana State University, USA)
Dimitris Simos (SBA Research, Austria)
Blerina Sinaimeri (INRIA, France)
Douglas Stinson (University of Waterloo, Canada)
Alexandru I. Tomescu (University of Helsinki, Finland)
Stephane Vialette (CNRS & University Paris-Est, France)
Lusheng Wang (City University of Hong Kong, SAR China)
Ian Wanless (Monash University, Australia)
Invited Speakers
Marinella Sciortino (University of Palermo)
Stephane Vialette (CNRS & University Paris-Est)
Ugo Vaccaro (University of Salerno)
Local Organizing Committee
Anna Bernasconi, Pisa
Alessio Conte, NII
Daniele Greco, Pisa
Roberto Grossi, Pisa
Veronica Guerrini, Pisa
Andrea Marino, Firenze
Nadia Pisanti, Pisa
Nicola Prezza, Pisa
Giulia Punzi, Pisa
Giovanna Rosone, Pisa
Rossano Venturini, Pisa
Steering Committee
Maria Chudnovsky (Princeton University, USA)
Charles Colbourn (Arizona State University, USA)
Costas Iliopoulos (King’s College London, UK)
Bill Smyth (McMaster University, Canada; Murdoch University,
Australia; King’s College London, UK)
Submissions
IMPORTANT DATES
(EXTENDED)February 27th 2019: Abstract due date
(EXTENDED) March 4th 2019: Paper due date
May 10th 2019: Notification
May 25th 2019: Camera ready
July 22nd 2019: StringMasters/GraphMasters
July 23rd - 25th 2019: IWOCA
GUIDELINES
We solicit high-quality proceedings papers in the broad area of combinatorial algorithms. The topics include (but are not restricted to):
Algorithms and Data Structures, Complexity Theory, Graph Theory & Combinatorics, Combinatorial Optimization, Cryptography & Information Security, Algorithms on Strings & Graphs, Graph Drawing & Labelling, Computational Algebra & Geometry, Computational Biology, Algorithms for Big Data and Networks Analytics, Probabilistic & Randomised Algorithms, New Paradigms of Computation
Proceedings papers cannot exceed 12 single-spaced pages, including references, figures, title, authors, affiliations, e-mail addresses, and a short (one paragraph) abstract. The authors are required to use the LaTeX style file supplied by Springer Verlag for Lecture Notes in Computer Science. Final proceedings papers must be camera-ready in this format. A clearly marked Appendix, which will not count toward the 12 page submission limit, can be included and will be read at the referees’ discretion.
All submissions have to be made via the EasyChair submission page for the conference at https://easychair.org/conferences/?conf=iwoca2019
Papers submitted for review should represent original, previously unpublished work and surveys of important results. At the time the paper is submitted to IWOCA, and for the entire review period, the paper (or essentially the same paper) should not be under review by any other conference with published proceedings or by a scientific journal. At least one author per each accepted paper will have to attend the conference and present the paper. Proceedings will be published in Springer Lecture Notes in Computer Science (LNCS) and made available at the Conference. Authors of selected papers will be invited to submit extended versions of their papers to a special issue of a journal.
Call for papers
IWOCA 2019 CALL FOR PAPERS
30th International Workshop on Combinatorial Algorithms
Department of Computer Science, University of Pisa, Italy
Pisa, July 23-25, 2019
Contact: iwoca2019@easychair.org
Conference website: http://iwoca2019.di.unipi.it
Submission link: https://easychair.org/conferences/?conf=iwoca2019
Associated events: StringMasters/GraphMasters 2019, July 22.
AIMS AND SCOPE
The series of IWOCA conferences grew out of over 30 years history of the International (since 2007) respectively Australasian (until 2006) Workshops on Combinatorial Algorithms. Previous IWOCA and AWOCA meetings have been held in Australia, Canada, Czech Republic, Finland, France, Indonesia, India, Italy, Japan, Singapore, South Korea, UK, and USA. Link to previous IWOCAs web pages can be found at https://nms.kcl.ac.uk/iwoca/previous.html
SUBMISSION GUIDELINES
We solicit high-quality proceedings papers in the broad area of combinatorial algorithms. The topics include (but are not restricted to):
Algorithms and Data Structures, Complexity Theory, Graph Theory & Combinatorics, Combinatorial Optimization, Cryptography & Information Security, Algorithms on Strings & Graphs, Graph Drawing & Labelling, Computational Algebra & Geometry, Computational Biology, Algorithms for Big Data and Networks Analytics, Probabilistic & Randomised Algorithms, New Paradigms of Computation
Proceedings papers cannot exceed 12 single-spaced pages, including references, figures, title, authors, affiliations, e-mail addresses, and a short (one paragraph) abstract. The authors are required to use the LaTeX style file supplied by Springer Verlag for Lecture Notes in Computer Science. Final proceedings papers must be camera-ready in this format. A clearly marked Appendix, which will not count toward the 12 page submission limit, can be included and will be read at the referees’ discretion.
All submissions have to be made via the EasyChair submission page for the conference at https://easychair.org/conferences/?conf=iwoca2019
Papers submitted for review should represent original, previously unpublished work and surveys of important results. At the time the paper is submitted to IWOCA, and for the entire review period, the paper (or essentially the same paper) should not be under review by any other conference with published proceedings or by a scientific journal. At least one author per each accepted paper will have to attend the conference and present the paper. Proceedings will be published in Springer Lecture Notes in Computer Science (LNCS) and made available at the Conference. Authors of selected papers will be invited to submit extended versions of their papers to a special issue of a journal.
IMPORTANT DATES
(EXTENDED)February 27th 2019: Abstract due date
(EXTENDED) March 4th 2019: Paper due date
May 10th 2019: Notification
May 25th 2019: Camera ready
July 22nd 2019: StringMasters and GraphMasters
July 23rd - 25th 2019: IWOCA
PROGRAM COMMITTEE
Charles Colbourn (co-chair, Arizona State University, USA), Roberto Grossi (co-chair, University of Pisa, Italy), Nadia Pisanti (co-chair, University of Pisa, Italy)
Hiroki Arimura (Hokkaido University, Japan), Hideo Bannai (Kyushu University, Japan), Philip Bille (Technical University of Denmark), Paola Bonizzoni (University of Milano Bicocca, Italy), Gerth Stolting Brodal (Aarhus University, Denmark), Maria Chudnovsky (Princeton University, USA), Dalibor Froncek (University of Minnesota - Duluth, USA), Travis Gagie (Diego Portales University, Chile), Serge Gaspers (UNSW Sydney and Data61, CSIRO, Australia), Dora Giammarresi (University of Roma Tor Vergata, Italy), Jan Holub (Czech Technical University in Prague, Czech Republic), Costas Iliopoulos (King’s College London, UK), Artur Jez (University of Wroclaw, Poland), Gregory Kucherov (CNRS & University of Paris Est, France), Gad Landau (University of Haifa, Israel), Thierry Lecroq (University of Rouen, France), Christos Makris (University of Patras, Greece), Sebastian Maneth (University of Bremen), Sabrina Mantaci (University of Palermo, Italy), Lucia Moura (University of Ottawa, Canada), Patric R. J. Östergård (Aalto University, Finland), Kunsoo Park (Seoul National University, South Korea), David Pike (Memorial University of Newfoundland, Canada), Solon Pissis (CWI Amsterdam, the Netherlands), Alexandru Popa (University of Bucharest, Romania), Rajeev Raman (University of Leicester, UK), Frank Ruskey (University of Victoria, Canada), Marinella Sciortino (University of Palermo, Italy) Rahul Shah (Louisiana State University, USA), Dimitris Simos (SBA Research, Austria), Blerina Sinaimeri (INRIA, France), Douglas Stinson (University of Waterloo, Canada), Alexandru I. Tomescu (University of Helsinki, Finland), Stephane Vialette (CNRS & University Paris-Est, France), Lusheng Wang (City University of Hong Kong, SAR China), Ian Wanless (Monash University, Australia)
LOCAL ORGANIZING COMMITTEE
Anna Bernasconi, Alessio Conte, Daniele Greco, Roberto Grossi, Veronica Guerrini, Andrea Marino, Nadia Pisanti, Nicola Prezza, Giulia Punzi, Giovanna Rosone, Rossano Venturini
STEERING COMMITTEE
Maria Chudnovsky (Princeton University, USA), Charles Colbourn (Arizona State University, USA), Costas Iliopoulos (King’s College London, UK), Bill Smyth (McMaster University, Canada; Murdoch University, Australia; King’s College London, UK)
Contact
For questions about the conference or the website contact the organizers via email
Venue
Pisa is a city in the Tuscany region of Central Italy, straddling the Arno river just before it reaches the sea. The city has today over 90,000 residents (around 200,000 with the metropolitan area), and according to an ancient legend it was founded by Greek refugees from the homonym Greek city of Pisa, close to Olympia in the valley of the Alfeo river, in the Peloponnese.
Among the most important monuments of the city is the famous Piazza del Duomo, also called Piazza dei Miracoli (Miracles Square), declared World Heritage Site, with the Cathedral built between 1063 and 1118 in Pisan Romanesque style and the Leaning Tower, bell tower of the twelfth century, today one of the most famous Italian monuments in the world because of its characteristic inclination. Despite being best known for its leaning tower and cathedral, Pisa has 20 other historic churches, several medieval palaces and various bridges across the Arno. Much of the city’s architecture was financed from its history as one of the more important maritime republics of Italy.
The city is also home of the University of Pisa, which has a history going back to the 12th century, the Scuola Normale Superiore di Pisa, founded by Napoleon in 1810, and its offshoot, the Sant’Anna School of Advanced Studies. Leonardo Fibonacci and Galileo Galilei are among the prominent scientists who were born in Pisa.
The conference will be held in the Computer Science department of the University of Pisa, at the address:
Dipartimento di Informatica
Università di Pisa
Largo Bruno Pontecorvo, 3
56127 Pisa
Travel and food information
Getting to Pisa. Pisa is served by the local International airport, Galileo Galilei located 4km from downtown. Several low-cost companies flow directiy to Pisa airport, one of the largest in Italy. There are daily flights from most european hubs, New York, as well as several other european cities served by low-cost companies – see e.g. a snapshot of today’s arrivals. If you don’t have a direct connection, you should be able to reach Pisa via Milan, Rome, London, Munchen, Paris, Frankfurt (Main), Brusselles (Charleroi) and New York.
Getting to the city center from the Airport of Pisa. The Pisa Airport is about 1 km from Pisa Centrale railway station, from which you can reach any Italian railway network destination. You can reach the center of the city by bus, taxi cab (tipically 15 euro), or using the high-speed, fully automatic People Mover service (located at less than 40 metres from the Passenger Terminal at the Pisa Airport) The latter service is available every day from 6:00 AM to midnight at 5/8 minute intervals.
Getting to Department of Computer Science. Please follow the map below to reach our Department (building C, second floor). The workshop venue is in its room Sala Gerace. Almost all places in Pisa are at walking distance.
Food in Pisa.
Several good and cheap places can be found around the Department. Click on the placeholders in the map below to get more information.
Registration
IMPORTANT NOTE: For each accepted paper, at least one author has to register as an author before the early bird deadline (please no on-site payment for author registration).
Registration form. Please fill the registration form that can be downloaded at this link selecting the appropriate fee.
Send the form via email to pisanti@di.unipi.it.
If paying by bank tranfer or credit card, please make the payment before sending the form, and attach proof to the email.
Payment via bank transfer. You can pay via bank tranfer specifying the following Purpose of payment:
-"IWOCA2019 + paperID + attendant name" (for author registration)
-"IWOCA2019 + attendant name" (otherwise)
To this account:
Bank Name: UNICREDIT, SOCIETA’ PER AZIONI
Bank Address: PIAZZA GARIBALDI, 1 ANG. LUNGARNO MEDICEO PISA 56126
Account Holder: COMITATO ORGANIZZATORE
IBAN: IT48M0200814006000105588591
Swift Code: UNCRITM1G12
Please note that the payments are due in EURO and all banking costs including exchange rates should be paid by the participant.
Payment via credit card.
In order to use your credit card, follow this link to fill a form for the invoice details. After sending the form, you will get an email with the actual link for the payment.
Payment on site (in cash).
Alternatively, you can pay cash on site at the conference, provided you have previously sent the registration form and ticked the choice ‘I will pay on site in cash’. A receipt for the payment will be issued.
Fees: | Early (by June 20th) |
Late (after June 20th) |
---|---|---|
Regular & Author | €430 | €530 |
Student | €300 | €400 |
Program/Steering Committee Member |
€400 | €500 |
On site (cash) | €400 provided registration form is sent by June 20th |
€500 please try sending the registration form before the conference |
Accompanying person |
€100 please write name in registration form |
PROCEEDINGS
The LNCS proceedings can be found by clicking the image below.
The online version of the proceedings is available at the link below.