Back to Top

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

Program at a Glance

Click/tap to open each map in a separate window or browser tab.

program at a glance

Track details

Click/tap to open each map in a separate window or browser tab.

track details

Monday, October 28

11:00-11:30 Opnening
11:30-12:30 Invited Talk by Takashi Horiyama, Saitama University, Japan
Enumeration with Isomorphism Elimination
Abstract
In many situations, we come across the symmetries of the instances. For example, a cube has 24 rotational symmetries (8 rotations by 120 degrees, 6 rotations by 90 degrees, 9 rotations by 180 degrees, and the identity). If we also take the inversion into consideration, the number of the symmetries will be doubled, i.e., a cube has 48 symmetries. If the elements of a given instance are labeled,f enumeration algorithms can use the labels. If, unfortunately, there are no labels, we are required to eliminate isomorphic solutions. For example, by cutting some edges of a cube, we can have its development. If we rotate the position of the cutting edges by 90 degrees, we again have a development. If the edges are labeled, we can distinguish these two developments by their labels. If they are not labeled, the two developments are of the same shape, i.e., they are isomorphic to each other. For the enumeration in this case, we cannot generate isomorphic developments twice. In this talk, we will discuss enumeration with isomorphism elimination.
12:30-14:00 Lunch Break
  Track A
14:00-14:30 Oscar Defrain and Lhouari Nourine
Dualization in lattices given by implicational bases
14:30-15:00 Oscar Defrain, Lhouari Nourine and Simon Vilmin
Translating between the representations of a ranked convex geometry
15:00-15:30 Katsuhisa Yamanaka, Takashi Horiyama, Yoshio Okamoto, Ryuhei Uehara and Tanami Yamauchi
Enumeration of Surrounding Polygons
15:30-16:00 Coffee Break
  Track B
16:00-16:30 Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno and Hiroki Arimura
A Constant Amortized Time Enumeration Algorithm for Independent Sets in Graphs with Bounded Clique Number
16:30-17:00 Hisao Tamaki
A simple algorithm for generating potential maximal cliques of a graph
17:00-19:00 Working Session

Tuesday, October 29

  Track C
9:00-9:30 Naveed Ahmed Azam, Aleksandar Shurbevski and Hiroshi Nagamochi
Counting Tree-Like Graphs with a Given Number of Vertices and Self-loops
9:30-10:00 Kazuya Haraguchi and Hiroshi Nagamochi
Experimental Comparison of Connector Enumeration Algorithms
10:00-10:30 Ester Livshits, Alireza Heidari, Ihab F. Ilyas and Benny Kimelfeld
Enumerating Approximate Denial Constraints
10:30-11:00 Coffee Break
11:00-12:00 Invited Talk by David Avis, Kyoto University and McGill University
The thirtieth year of reverse search
Abstract
In October 1990 Komei Fukuda and I were discussing the criss-cross method for linear programming and realized that by "reversing it" we could visit all the vertices of an arrangement of hyperplanes. A curiousity we thought. However, the next day we realized that by replacing the criss-cross method by Bland's rule we could generate all vertices of a polyhedron, a much more interesting problem. Reverse search was born. Since then it has found its way into many hundreds of applications and related codes. I will begin by reviewing some early history and then introduce the MTS framework that Skip Jordan and I have developed to parallelize existing reverse search (and other tree search) codes.
12:00-14:00 Lunch Break & Business Meeting
  Track D
14:00-14:30 Kensuke Onishi and Takeaki Uno
A computation method of minimum-comparison sorting network using SeqBDD
14:30-15:00 Shin-Ichi Minato
Depth-First ZDD Construction with Frontier-Based Search Method for Graph Enumeration Problems
15:00-15:30 Yu Nakahata, Jun Kawahara and Shin-Ichi Minato
Decision-Diagram-Based Enumeration of d-Cutsets
15:30-16:00 Coffee Break
16:00-19:00 Working Session

Wednesday, October 30

  Track E
9:00-9:30 Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld and Moshe Sebag
The Shapley Value of Tuples in Query Answering
9:30-10:00 Christoph Berkholz, Nofar Carmeli, Benny Kimelfeld, Nicole Schweikardt and Shai Zeevi
Random Access and Random Permutation of Answers to Conjunctive Queries
10:00-10:30 Antoine Amarilli, Benny Kimelfeld and Stefan Mengel
Skyline Operators for Document Spanners
10:30-11:00 Alessio Conte, Roberto Grossi, Giulia Punzi and Takeaki Uno
Polynomial-Delay Enumeration of Maximal Common Subsequences
11:00-11:30 Coffee Break
11:30-12:30 Invited Talk by Serge Gaspers, The University of New South Wales, Australia
Probabilistic methods in input-sensitive enumeration
Abstract
In this talk, a new technique for subset enumeration problems is discussed. The technique was originally designed for subset optimization and decision problems, but translates seamlessly to combinatorial upper bounds and enumeration algorithms. For an instance of size n, assume enumerating all desired sets of size at most k takes time c^k poly(n), for some constant c. Then, under some mild assumptions, our technique gives an enumeration algorithm for all desired sets with total running time (2-1/c)^(n+o(n)). I will present this technique and its analysis, along with extensions and applications.
This is joint work with Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh (STOC 2016 and JACM 2019), Edward J. Lee (ICALP 2017), and Ray Li (MFCS 2019).
12:30-14:00 Lunch Break
14:00-19:00 Excursion
19:00-24:00 Banquet

Thursday, October 31

  Track F
9:00-9:30 Johann Birnick, Thomas Bläsius, Tobias Friedrich, Thorsten Papenbrock and Martin Schirneck
Enumerating Unique Column Combinations with a Sample-And-(Don't)-Restart Strategy
9:30-10:00 Benjamin Bergougnoux, Mamadou Kanté and Kunihiro Wasa
Disjunctive Minimal Separators Enumeration
10:00-10:30 Alice Raffaele and Romeo Rizzi
A new decomposition for the Monotone Boolean Duality problem
10:30-11:00 Coffee Break
11:00-12:00 Invited Talk by Koji Tsuda,
Statistically Sound Data Mining
Abstract
Recently Financial Times published an article entitled “Big data: are we making a big mistake?". It points out that data mining methods produce too many results and it is hard to distinguish real discoveries from false ones. Actually, analyzers tend to hand-pick convincing results and present them to customers/reviewers/bosses, hiding existence of unwanted results. This is a very bad practice, because it always results in rediscovery of popular knowledge. New and real discoveries are overlooked because they do not look familiar. I will present a new technique called LAMP (Limitless Arity Multiple testing Procedure) to evaluate the reliability of data mining results in terms of statistical significance. In addition, I introduce a new line of research called selective inference. Most results are biological but underlying principles are relevant to all kinds of data analysis.
12:00-14:00 Lunch Break
  Track G
14:00-14:30 Alessio Conte and Takeaki Uno
Proximity Search For Maximal Subgraph Enumeration
14:30-15:00 Alessio Conte, Roberto Grossi, Andrea Marino and Luca Versari
Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
15:00-15:30 Caroline Brosse, Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary and Lucas Pastor
Enumeration of maximal induced Π-subgraphs and minimal Π-completions
15:30~ Closing

Registration

Registration fee 0 yen.

To register online, click one of the links below that matches your preference:

  1. Conference Attendance Only
  2. Conference and Banquet Attendance
  3. Conference, Banquet Attendance and Hotel Booking

Please complete only one registration form. Registration will be free this year i.e. 0 yen. Please note that for participants wanting to book a room at the Yumekaiyu Awajishima hotel through us (Option 3), the deadline has been extended and will be announced later. Please complete your registration as soon as possible as the number of rooms we are able to reserve is limited.


About Hotel Booking

For participants wanting to book a room through us, please let us know which type of room you prefer: a shared room (12,000 yen per night) or a single room (16,000 yen per night). We will temporarily book the room for you. If you cannot attend, we can cancel. There are also other hotels around the conference site, so you can make your own reservations at a later date. In that case, you will only need to pay for the banquet fee if you want to attend.


WEPA Travel Support

  • We can offer support for flight tickets and/or fees for hotel, and local transportation.
  • When we cover your flight costs, we will pay for all, but only from your home town to the conference site. There are many conditions for this funding so please do not rush to buy a ticket before consulting with us.
  • In principle we would like to provide support to as many participants as possible who require the extra funding. Please consider whether you really need the funding before applying e.g. you have no other institutional support. This is so that we can ensure that the support can be fairly distributed to participants who would otherwise not be able to attend.
  • Travel support is paid from the personal budget of Prof. Takeaki Uno of NII, Japan.

The PC members will select the candidates, with consideration given to the following factors:

  1. participants who will have a talk at WEPA 2019
  2. participants who have some prior work on enumeration algorithms
  3. participants whose supervisor have prior work on enumeration algorithms
  4. participants who can pay for either their own flight ticket or hotel fee

We will select the candidates and determine the funding provided after notification of the acceptance in late September. If you wish to book a room through us, please let us know which type of room you prefer: a shared room (12,000 yen per night) or a single room (16,000 yen per night). We will temporarily book the room for you. If you cannot attend, we can cancel.

Venue

According to the ancient Japanese literature, Kojiki and Nihon Shoki, Awaji Island is said to be the first island that formed for Japan. There are many locations that are related to the legends of how this nation was born. The beautiful nature, historic culture, abundant cuisine, and countless hotsprings are among the charms of Awaji Island that you can experience. For more information visit the Awaji Island Tourism Guide.

Group picture

The conference will be held at the Yumekaiyu Awajishima hotel, located at: 1 Chome-1-50 Yamate, Sumoto, Hyogo 656-0024

For more information visit the Yumekaiyu Awajishima website.

Group picture

Access

To reach Awaji Island and the Yumekaiyu Awajishima hotel, you will need to take a bus or other road transport via Kobe city. There is no train or Shinkansen (bullet train) access to the island. We have listed some common access routes below. In most cases you will need to travel to the Sumoto Bus Center on Awaji Island where you can then take a free shuttle bus to the hotel. We have also provided an access map (pdf link here and also see below to download separate maps) if you are unfamiliar with the Osaka-Kobe area.

For more information, please visit the Awaji Island tourism access page (English) and the Yumekaiyu Awajishima hotel access page - (Japanese, requires browser translation). Also for an English language guide to buses running from Kobe to the Sumoto Bus Center, please consult this site managed by Awaji Island residents.

From Osaka (Umeda Station)
  1. 120 minutes by high-speed bus.
  2. Arrive at Sumoto Bus Center.
  3. Free hotel shuttle bus from bus center about 5 minutes.
From Kobe (Shin Kobe Station)
  1. 100 minutes by high-speed bus.
  2. Arrive at Sumoto Bus Center.
  3. Free hotel shuttle bus from bus center about 5 minutes.
From Kobe (Sannomiya Station)
  1. 80 minutes by high-speed bus.
  2. Arrive at Sumoto Bus Center.
  3. Free hotel shuttle bus from bus center about 5 minutes.
Timetable for Free Hotel Shuttle Bus

Timetable for pickups and drop-offs via the free hotel shuttle bus from Sumoto bus center is here. The page is in Japanese only however you can translate via Google. Note that this bus travels via other hotels.

  • The first table contains departure times from the Sumoto Bus Centre. The blue column is for arrival times at the Yumekaiyu Awajishima hotel.
  • The second larger table contains departure times from the Yumekaiyu Awajishima hotel to the Sumoto Bus Centre. The blue column lists the departure times.

Kobe Airport
  1. Port liner train approximately 18 minutes.
  2. Arrive at Sannomiya Station.
  3. High-speed bus about 90 minutes.
  4. Arrive at Sumoto Bus Center.
  5. Free hotel shuttle bus from bus center about 5 minutes.
Osaka International Airport (Itami Airport)
  1. Limousine bus about 40 minutes to Sannomiya Station.
  2. High-speed bus about 90 minutes to Sumoto Bus Center.
  3. Free hotel shuttle bus from bus center about 5 minutes.
Kansai International Airport (Route 1)
  1. Limousine bus about 65-80 minutes to Sannomiya Station.
  2. High-speed bus about 90 minutes to at Sumoto Bus Center.
  3. Free hotel shuttle bus from bus center about 5 minutes.
Kansai International Airport (Route 2)
  1. Limousine bus about 120 minutes direct to Sumoto Interchange.
  2. Taxi about 15 minutes to hotel.
Timetable for Free Hotel Shuttle Bus

Timetable for pickups and drop-offs via the free hotel shuttle bus from Sumoto bus center is here. The page is in Japanese only however you can translate via Google. Note that this bus travels via other hotels.

  • The first table contains departure times from the Sumoto Bus Centre. The blue column is for arrival times at the Yumekaiyu Awajishima hotel.
  • The second larger table contains departure times from the Yumekaiyu Awajishima hotel to the Sumoto Bus Centre. The blue column lists the departure times.

From Osaka Station
  1. JR Kobe line rapid train, 25-30 minutes.
  2. Arrive at Sannomiya Station (Kobe).
  3. High-speed bus about 90 minutes.
  4. Arrive at Sumoto Bus Center.
  5. Free hotel shuttle bus from bus center about 5 minutes.

Note: If you are in the Osaka City area, you can reach Osaka Station via the JR Osaka Loop line or Osaka city subway. The subway stop is Umeda (M16) which is in the same station complex as JR Osaka (you will have to walk to the JR train line area).

Timetable for Free Hotel Shuttle Bus

Timetable for pickups and drop-offs via the free hotel shuttle bus from Sumoto bus center is here. The page is in Japanese only however you can translate via Google. Note that this bus travels via other hotels.

  • The first table contains departure times from the Sumoto Bus Centre. The blue column is for arrival times at the Yumekaiyu Awajishima hotel.
  • The second larger table contains departure times from the Yumekaiyu Awajishima hotel to the Sumoto Bus Centre. The blue column lists the departure times.

Click/tap to open each map in a separate window or browser tab.

access map via trains access map from Tokyo airports access map to Sumoto bus centre

Committees

Program Committee

Takeaki Uno - PC Chair (National Institute of Informatics, Japan)
Endre Boros (Rutgers University, USA)
Mamadou Moustapha Kanté (Université Clermont Auvergne, France)
Benny Kimelfeld (Technion - Israel Institute of Technology, Israel)
Masashi Kiyomi (Yokohama City University, Japan)
Andrea Marino (Università degli Studi di Firenze, Italy)
Arnaud Mary (University Claude Bernard Lyon 1, France)
Lhouari Nourine (Université Clermont Auvergne, France)
Yann Strozecki (The University of Versailles Saint-Quentin)
Katsuhisa Yamanaka (Iwate University, Japan)
Kunihiro Wasa (National Institute of Informatics, Tokyo)

Local Organizing Committee

Kaori Deguchi - Local Organizer
Takeaki Uno - Chair
Arnaud Mary
Kunihiro Wasa

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 (click link to open electronic submission page). Invited papers and accepted contributions will be invited to contribute to a special issue in a journal.

Group picture

Call for Papers

WEPA 2019: Third Workshop on Enumeration Problems and Applications October 28-31, Yumekaiyu Awajishima, in Hyogo (Japan)

The WEPA 2019 conference is the Third Workshop on Enumeration Problems and Applications. It will take place at Yumekaiyu Awajishima, in Hyogo (Japan). The conference will take place from October 28th (Monday) to October 31st (Thursday), 2019.

Important Dates

Submission Deadline: September 13, 2019
Notification: September 27, 2019
Conference: October 28 - 31, 2019

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, etc)
  • Input-sensitive algorithms
  • Output-sensitive algorithms

Invited Speakers

David Avis (McGill University and Kyoto University)
Serge Gaspers (The University of New South Wales, Australia)
Takashi Horiyama (Saitama University, Japan)
Koji Tsuda (Tokyo University, Japan)

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 (click link to open electronic submission page). Invited papers and accepted contributions will be invited to contribute to a special issue in a journal.