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
 

Sponsors


PROCEEDINGS

The LNCS proceedings can be found by clicking the image below.


The online version of the proceedings is available at the link below.

ONLINE LNCS PROCEEDINGS