2nd International Workshop on
Enumeration Problems & Applications
5-8 November 2018
Workshop supported by the National Institute of Informatics, Japan, and by the University of Pisa
Aims and Scope
WEPA is a new international forum for researchers in the area of design, analysis, experimental evaluation and engineering of algorithms for enumeration problems on graphs, strings, and other domains. The objective of the workshop is to gather researchers working in enumeration algorithms, including their applications in Biology, Data Mining, Logic, and Database. The goal is to present recent results, identify and explore directions for future research, and foster collaborations.
Program
Monday, November 5
| 8.45-9.15 | Welcome and Registration |
| 9:15-9:20 | Greetings from the Vice-Rector Franco Turini (U. Pisa) |
| 9:20-10.20 | Invited Lecture by Marie-France Sagot (INRIA & Université Claude Bernard, Lyon 1) Looking for a needle (maybe a needle) in a haystack (maybe a haystack) |
| 10.20-10.40 | Coffee Break |
| Session 1 | |
| 10.45-11.15 | Sarah Blind, Nadia Creignou and Frédéric Olive Locally definable vertex set properties are enumerable in linear delay |
| 11.15-11.45 | George Manoussakis and Danny Hermelin Efficient Enumeration of Maximal Induced Bicliques |
| 11.45-12.15 | Petr Golovach, Pinar Heggernes, Dieter Kratsch and Reza Saei Enumeration of Minimal Connected Dominating Sets for Chordal Graphs |
| 12.15-14.00 | Lunch Break (on your own) |
| Session 2 | |
| 14.00-15.00 | Invited Lecture by Benny Kimelfeld (Technion - Israel Institute of Technology) Some Clique Enumerations in Database Management |
| 15.00-15.30 | Oscar Defrain, Lhouari Nourine and Takeaki Uno Ideal-preferred enumeration toward distributive lattice dualization |
| 15.30-16.00 | Coffee Break |
| Session 3 | |
| 16.00-16.30 | Christian Bean, Michael Albert, Anders Claesson, Jay Pantone and Henning Ulfarsson Combinatorial exploration |
| 16.30-17.00 | Alessio Conte, Roberto Grossi, Andrea Marino and Luca Versari Efficient Enumeration of Maximal Common Subgraphs |
| 17.00-17.30 | Nofar Carmeli and Markus Kröll Enumeration Complexity of Unions of Conjunctive Queries |
| 19.30-21.30 | Dinner at Le Scuderie (your confirmation required) |
Tuesday, November 6
| Session 4 | |
| 9.00-9.30 | Takeaki Uno Constant Time Enumeration for Connected k-Subgraphs |
| 9.30-10.00 | Alessio Conte, Donatella Firmani, Maurizio Patrignani and Riccardo Torlone A Meta-Algorithm for Finding Large k-Plexes |
| 10.00-10.30 | Coffee Break |
| Session 5 | |
| 10.30-11.00 | Sarah Blind, Kolja Knauer and Petru Valicov Enumerating k-arc-connected orientations |
| 11.00-11.30 | Yann Ponty, Sebastian Will and Stefan Hammer Nucleic Acids design targeting integer-valued features: FPT counting and uniform sampling |
| 11.30-12.00 | Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno and Hiroki Arimura Subgraph Enumeration: Efficient Algorithms and Empirical Studies |
| 12.00-14.00 | Lunch Break (on your own) |
| 14.00-15:00 | Invited Lecture by Fedor Fomin (University of Bergen) How many objects in a graph? Bounds and enumeration |
| 15.00-15:30 | Coffee Break |
| 15:30-16.30 | Open Problem Session |
| 16:30-19:00 | Open Discussion |
| 20:00-22:00 | Dinner at Cereria alle Porte (your confirmation required) |
Wednesday, November 7
| 9.30-10:00 | Kazuya Haraguchi, Yusuke Momoi, Aleksandar Shurbevski and Hiroshi Nagamochi COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets |
| 10.00-10.30 | Group Picture and Coffee Break |
| Session 6 | |
| 10.30-11.00 | Romeo Rizzi and Alice Raffaele A Joint Generation Approach for the Vertex Enumeration Problem |
| 11.00-11.30 | Amihood Amir, Samah Ghazawi, Concettina Guerra, Gad M. Landau and J. Rossignac Classification of Permutations Using PQ-trees |
| 11.30-12.00 | Naveed Ahmed Azam, Ito Mawo, Aleksandar Shurbevski and Hiroshi Nagamochi Enumerating All Pairwise Compatibility Graphs with a Given Number of Vertices Based on Linear Programming |
| 12.00-14.00 | Lunch Break (on your own) |
| Session 7 | |
| 14.00-15.00 | Invited Lecture by Endre Boros (Rutgers University) Parallel Hypergraph Dualization |
| 15.00-15.30 | Coffee Break |
| 15.30-16.30 | Open Problems Session |
| 16.30-19:00 | Open Discussion |
| 20:00-22.00 | Dinner at Osteria di Culegna (your confirmation required) |
Thursday, November 8
| 9.00-10.00 | Invited Lecture by Shin-ichi Minato (Kyoto University) Decision Diagram-Based Techniques for Enumeration Problems and Applications |
| 10.00-10.30 | Coffee Break |
| Session 8 | |
| 10.30-11.00 | Alessio Conte, Tiziano De Matteis, Daniele De Sensi, Roberto Grossi, Andrea Marino and Luca Versari D2K: Theory and Practice Combined for Fast k-Plex Enumeration |
| 11.00-11.30 | Filippo Disanto Enumerative properties of gene tree configurations in matching species trees |
| 11.30-12.00 | Shoya Takahashi, Shin-Ichi Minato and Ichigaku Takigawa Enumerating and Indexing Set Partitions Using Sequence BDDs |
| 12.00-14.00 | Lunch Break (on your own) |
| Session 9 | |
| 14.00-14.30 | Vincenzo Bonnici, Simone Caligola, Antonino Aparo and Rosalba Giugno Computational strategies and algorithmic insights to speed the sub-isomorphism searches up |
| 14.30-15.00 | Takashi Horiyama and Takefumi Kondo On the Enumeration of the Nonisomorphic Unfoldings of 4-Dimensional Crosspolytopes |
| 15.00-15.30 | Coffee Break |
| 15.30-17:00 | Open Discussion |
| 17:00 | Farewell |
Registration
There is no registration fee for WEPA this year. However, the organization recalls that it is mandatory to register before 20 October 2018 by sending a message to wepa2018nov@gmail.com specifying the following information:
- name and affiliation
- which days you plan to attend WEPA (from Nov. 5th to 8th)
- which days you plan to have dinner together with the other participants (from Nov. 5th to 7th, any accompanying persons?)
- dietary restrictions
WEPA organization is happy to offer coffee breaks. Unfortunately it cannot offer meals and accommodation, which you have to provide by yourself (see map below for places to go eating at reasonable price).
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.
Lunch in Pisa.
Lunch is on your own, several good and cheap places can be found around the Department. Click on the placeholders in the map below to get more information.
Dinner in Pisa.
We organize dinner for the first three days (Nov. 5-7). Everyboy is welcome but please send us a message to confirm your attendance, so that we can reserve enough tables. An email has been sent to the registered people reporting who confirmed her/his interest to the dinners.
| Nov. 5 | 19:30 | Le Scuderie, Via Simone Sancasciani 1 | check map |
| Nov. 6 | 20:00 | Cereria alle Porte, Viale Francesco Bonaini 1 | check map |
| Nov. 7 | 20:00 | Osteria di Culegna, Via Mercanti 25 | check map |
Program Committee
Hiroki Arimura (Hokkaido University)
Endre Boros (Rutgers)
Alessio Conte (National Institute of Informatics, Tokyo)
Nadia Creignou (Aix-Marseille Université)
Fedor Fomin (University of Bergen)
Petr Golovach (University of Bergen)
Benny Kimelfeld (Technion - Israel Institute of Technology)
Andrea Marino - PC Chair (University of Pisa)
Arnaud Mary (Laboratoire de Biométrie et Biologie Évolutive, Lyon)
Shin-ichi Minato (Kyoto University)
Lhouari Nourine (University Blaise Pascal, Aubiere)
Romeo Rizzi (University of Verona)
Marie-France Sagot (Inria & Laboratoire de Biométrie et Biologie Évolutive, Lyon)
Takeaki Uno - PC Chair (National Institute of Informatics, Tokyo)
Kunihiro Wasa (National Institute of Informatics, Tokyo)
Local Organizing Committee
Alessio Conte
Roberto Grossi - Chair
Shima Moghtasedi
Luca Versari
Submissions
Contributors are invited to submit an extended abstract of at most 2 pages (excluding the references), submitting the paper electronically using EasyChair (https://easychair.org/conferences/?conf=wepa2018). Invited papers and accepted contributions will be invited to contribute to a special issue in a journal. Simultaneous submission of papers to any other conference which proceedings are published or made publicly available, or submitting papers previously accepted for journal publication, is allowed and must be indicated in the submission.
Call for papers
WEPA 2018: Second Workshop on Enumeration Problems and Applications
November 5-8, Department of Computer Science, University of Pisa, Pisa
Submission Deadline: Sep 3 Sep 10, 2018 (AoE)
Notification: Sep 25 Sep 30, 2018
The WEPA 2018 conference is the Second Workshop on Enumeration Problems and Applications. It will take place at Department of Computer Science of University of Pisa, in Pisa (Italy). The conference will take place from Monday November 5 to Tuesday November 8, 2018.
Important Dates
Submission of papers: Sep 3 Sep 10, 2018 (AoE)
Acceptance notification: Sep 25, 2018 Sep 30, 2018
Registration: Oct 20, 2018
Conference: Nov 5-8, 2018
Website: wepa2018.di.unipi.it
Aims and Scope
WEPA is a new international forum for researchers in the area of design, analysis, experimental evaluation and engineering of algorithms for enumeration problems. The objective of the workshop is to gather researchers working in enumeration algorithms, including their applications in Biology, Data Mining, Logic, and Database. The goal is to present recent results, identify and explore directions for future research, and foster collaborations.
For this reason, along with the sessions for the presentation of established results, this year WEPA will introduce new sessions that are devoted to ideas, sketches, and open problems: hopefully this will put in touch senior researchers with junior researchers and graduate students to investigate problems of theoretical and practical interest. These new sessions will be informal, with no scheduled presentations, entirely devoted to the interactions among the participants. The workshop will be accommodated some rooms to allow space for the parallel working groups.
Submissions to WEPA should describe results in any area of enumeration problems and including, but not restricted to:
- Applications in Biology, Data Mining, Logic, and Database
- Approximate enumeration and counting
- Combinatorial enumeration and counting (hypergraph dualization, lattices, functional dependencies,…)
- Input-sensitive algorithms
- Output-sensitive algorithms
There is no registration fee for WEPA this year. However, it is mandatory to register before 20 October 2018 by sending a message to wepa2018nov@gmail.com
Submissions and Proceedings
Contributors are invited to submit an extended abstract of at most 2 pages (excluding the references) to be submitted electronically using EasyChair at the link https://easychair.org/conferences/?conf=wepa2018. Invited papers and accepted contributions will be invited to contribute to a special issue in a journal.
Contact
For questions about the conference or the website contact the organizers via email or the WEPA 2018 Facebook Page