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

9.00-9.15 Welcome
9.15-10.15 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.15-10.45 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
  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



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 Filippo Disanto
Enumerative properties of gene tree configurations in matching species trees
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
14.00-15.00 Invited Lecture by Fedor Fomin (University of Bergen)
Enumeration algorithms via monotone local search
15.00-15.30 Coffee Break
15.30-16.30 Open Problem Session
16.30-19:00 Open Discussion
20.00 Social Dinner



Wednesday, November 7

9.00-10.00 Invited Lecture by Endre Boros (Rutgers University)
Parallel Hypergraph Dualization
10.00-10.30 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 Simone Faro and Arianna Pavone
Flexible and Efficient Algorithms for Counting Abelian Matches in Strings
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
  Session 7
14.00-14.30 Kazuya Haraguchi, Yusuke Momoi, Aleksandar Shurbevski and Hiroshi Nagamochi
COOMA: A Components Overlaid Mining Algorithm for Enumerating Connected Subgraphs with Common Itemsets
14.30-15.00 A. Amir, Samah Ghazawi, C. Guerra, Gad M. Landau and J. Rossignac
Classification of Permutations Using PQ-trees
15.00-15.30 Coffee Break
15.30-16.30 Open Problems Session
16.30 Open Discussion



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 Yann Ponty, Sebastian Will and Stefan Hammer
Nucleic Acids design targeting integer-valued features: FPT counting and uniform sampling
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
  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 Departure



Events will also be announced on the WEPA 2018 Facebook Page

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.

Eating in Pisa.

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