The 22nd Korea-Japan Joint Workshop on Algorithms and Computation

This annual workshop has a long tradition of scientific collaboration and academic friendship between neighboring countries that will continue unaffected by political fluctuations.

The aim of this workshop is to provide a forum for researchers working on algorithms and the theory of computation, to promote the exchange of recent results, to foster new collaborations among researchers. Historically, the workshop has been established for the purpose of collaboration of researchers of Korea and Japan; however, participation from any country is welcome.

The workshop is organized by the Special Interest Group on Algorithms (SIGAL) of the Information Processing Society of Japan and the Special Interest Group on Theoretical Computer Science (SIGTCS) of the Korean Institute of Information Scientists and Engineers (KIISE).

The topics covered by the workshop are, but not limited to:

• Automata, languages and computability
• Algorithms (combinatorial/graph/geometric/randomized)
• VLSI and parallel algorithms
• Networks and distributed algorithms
• Learning theory and data mining
• Number theory and cryptography
• Graph drawing and visualization
• Computational logic
• Combinatorics and optimization

Prof. Hirotaka Ono, Nagoya University.

Algorithms  for Distance Constrained Labeling

Distance constrained labeling problems, e.g., L(p, q)-labeling and (p, q)-total labeling, are concerned with labeling on vertices of graphs, which are originally motivated by the frequency assignment. The upper bounds on the labeling numbers and the time complexity of finding a minimum labeling are intensively and extensively studied. In this talk, we introduce several results on algorithms for distance constrained labeling problems.

Authors are invited to submit papers up to 8 pages in English via the EasyChair submission system no later than August 26, 2019 August 31, 2019.

Since the proceedings will be only distributed at the workshop, submission of preliminary or extended versions of materials that are to appear in other conferences or journals is allowed and encouraged.

The paper must be written in English. The camera-ready version must be printed to fit A4 size sheet. It cannot exceed 8 pages including the title page. The first page must be in single column style although the following pages could be in double columns. The first page should contain the title, authors, affiliations, addresses (including authors’ e-mail addresses), and abstract.

Call for Papers (PDF)

Submission deadline: August 26, 2019 August 31, 2019

Notification of acceptance: September 10, 2019 September 15, 2019

Final version submission: September 18, 2019 September 23, 2019

Early registration: September 20, 2019

German Octoberfest in Korea: Oct 3-5, 2019

Conference: October 4~5, 2019

• Sang Won Bae (Kyonggi University)
• Yo-Sub Han (Yonsei University)
• Taisuke Izumi (Nagoya Institute of Technology)
• Naonori Kakimura (Keio University)
• Akitoshi Kawamura (Kyushu University)
• Heejin Park, co-chair (Hanyang University)
• Eiji Takimoto, co-chair (Kyushu University)
• Martin Ziegler (KAIST)

Organizing Committee Martin Ziegler, Svetlana Selivanova, Sewon Park

Important: Workshop venue has changed:

The workshop takes place in Chung Kunmo Conference Hall (정근모컨퍼런스홀), 5th floor, Academic Cultural Complex (학술문화관) (E9 Building), KAIST Main Campus, Daejeon

• Address: KAIST, 291 Daehak-ro, Yuseong-gu, Daejeon 34141, Republic of Korea
• See also the venue in Google Map

It is the easiest to get to the conference hall when you enter the building from south and take an elevator to the 5th floor.

There are a few options for transportation to Daejeon:

• AREX from Incheon Airport to Seoul, then KTX to Daejeon Station
  • Take the Express AREX to Seoul Station and there change to any of the daily KTX to Daejeon.

• AREX from Gimpo International Airport to Seoul, then KTX to Daejeon Station
  • From Gimpo, take the All-Stop AREX to Seoul Station, then proceed as above.

• Express Bus from Incheon Airport to Daejeon Government Complex
  • it may be most convenient to take the direct express bus between Incheon airport and Daejeon Government complex: 大田 政府庁 https://txbuse.t-money.co.kr/ The bus leaves at terminal 1 from bus stop 11A, at terminal from bus stop 5. https://www.airport.kr/ap_lp/ja/tpt/pblctpt/busstoinft1/busstoinft1.do It runs roughly every 20 minutes and takes about 3h, including a short rest of 15 minutes half-way and brief calls at other stops in Daejeon. Tickets (only with assigned seats) are purchased at multilingual vending machines or at kiosk with multilingual staff for 23,100 KRW.

• Express/Intercity Bus from Gangam to Daejeon
  • In the southern part of Seoul (Gangnam) there are two close-by bus terminals: Express and Central City. They serve several (often disjoint) destinations within Daejeon:

• Taxi to KAIST or to your hotel
  • Taxis are really inexpensive in Korea! In front of Daejeon Station, wait in line for the next one available; fare should be around 11,000 KRW; similarly from Express Bus Station Daejeon Terminal Complex (East Daejeon); from Government Complex around 8,000 KRW; and from Yuseong Bus Terminal around 6,000 KRW.

• Subway from Daejeon Station
  • Daejeon's Toyoko Inn (see below) is close to the aforementioned Subway station Government Complex. KAIST is not so close to station Wolpyeong, so we rather recommend taking a taxi right away. Subway can be conveniently accessed with a T-Money card that also works for city busses in Daejeon, taxis, convenience stores etc.

Here are some recommended hotels:

• Toyoko Inn Daejeon Government Complex: good location, average prices.
• Daedeok Innopolis Guest House: good location, inexpensive prices. (The website is in Koeran. Alternatively, reservation can be made through email: guesthouse@innopolis.or.kr)
• Many further options…

Fill in the form on the registration page to register for the workshop.

Registration fee will be collected on-site either by cash or credit card. A certificate for the registration fee payment will be published by the organizing committee. When an official receipt is required, it will be published by KIISE after the workshop; in this case, please contact the organizing committee waac2019[at]theoryofcomputation.asia.

Registration fee includes the workshop banquet dinner scheduled on October 4th.

1. Early Registration (until 24:00, September 20)
   1. Student: 50,000KRW
   2. Regular: 150,000KRW
2. Regular Registration (after 00:00, September 21)
   1. Student: 75,000KRW
   2. Regular: 200,000KRW

Extended Abstracts (password-protected)

• Tetsuo Asano, Naoki Katoh and Takeshi Tokuyama “Near-unit distance embedding of points in the plane and space”
• Hyunwoo Lee, Martin Ziegler, Willem Fouche, Donghyun Lim, Sewon Park and Matthias Schröder “Random Sampling of Continuous Objects: Can we Computably Generate Brownian Motions?”
• Xinhu Lan, Aleksandar Shurbevski and Hiroshi Nagamochi “A Routing Problem in Warehouse Graphs”
• Ryota Yonekura, Hidefumi Hiraishi and Hiroshi Imai “BDD of Eulerian Subgraphs and Computation of the Ising Partition Function”
• Sung Gwan Park, Amihood Amir, Gad M. Landau and Kunsoo Park “A New Generalized Matching Problem Based on Cartesian Trees”
• Myounji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park and Wook-Shin Han “An Efficient Algorithm for Subgraph Isomorphism”
• Yusuke Sawada, Yonghwan Kim and Yoshiaki Katayama “A Self-optimizing Three Nodes Routing Algorithm based on local information in Virtual Grid Networks”
• Ryo Yahagi, Yonghwan Kim and Yoshiaki Katayama “A Parallel Branch-and-Bound Method using MapReduce and HBase”
• Ivan Adrian Koswara, Gleb Pogudin, Svetlana Selivanova and Martin Ziegler “Computational Complexity of Real Matrix Powering”
• Hyunwoo Lee, Youngjo Min and Martin Ziegler “Analytic Continuation in Exact Real Computation”
• Seokbin Lee, Donghyun Lim, Sewon Park and Martin Ziegler “Grassmannian as Continuous Abstract Data Type with Computable Semantics”
• Holger Thies and Florian Steinberg “Computable analysis and verified exact real computation in Coq (Extended Abstract)”
• Donghyun Lim “Solving the Game of Har-mo-ny by Heuristics”

Day 1: Friday, October 4

9.20-9.50 Registration

9.50-10.00 Welcome address

10.00-11.00 Invited talk: Hirotaka Ono. Algorithms  for Distance Constrained Labeling

11.00-11.30 Coffee break

11.30-12.00 Ryota Yonekura, Hidefumi Hiraishi and Hiroshi Imai. BDD of Eulerian Subgraphs and Computation of the Ising Partition Function

12.00-12.30 Myoungji Han, Hyunjoon Kim, Geonmo Gu, Kunsoo Park and Wook-Shin Han. An Efficient Algorithm for Subgraph Isomorphism

12.30-14.00 Lunch break

14.00-14.30 Tetsuo Asano, Naoki Katoh and Takeshi Tokuyama. Near-unit distance embedding of points in the plane and space

14.30-15.00 Sung Gwan Park, Amihood Amir, Gad M. Landau and Kunsoo Park. A New Generalized Matching Problem Based on Cartesian Trees

15.00-15.30 Yusuke Sawada, Yonghwan Kim and Yoshiaki Katayama. A Self-optimizing Three Nodes Routing Algorithm based on local information in Virtual Grid Networks

15.30-16.00 Coffee break

16.00-16.30 Holger Thies and Florian Steinberg. Computable analysis and verified exact real computation in Coq

16.30-17.00 Seokbin Lee, Donghyun Lim, Sewon Park and Martin Ziegler. Grassmannian as Continuous Abstract Data Type with Computable Semantics

17.00-17.30 Hyunwoo Lee, Youngjo Min and Martin Ziegler. Analytic Continuation in Exact Real Computation

18.00 Banquet

Day 2: Saturday, October 5

9.30-10.00 Xinhu Lan, Aleksandar Shurbevski and Hiroshi Nagamochi. A Routing Problem in Warehouse Graphs

10.00-10.30 Ryo Yahagi, Yonghwan Kim and Yoshiaki Katayama. A Parallel Branch-and-Bound Method using MapReduce and HBase

10.30-11.00 Coffee break

11.00-11.30 Donghyun Lim. Solving the Game of Har-mo-ny by Heuristics

11.30-12.00 Hyunwoo Lee, Martin Ziegler, Willem Fouche, Donghyun Lim, Sewon Park and Matthias Schröder. Random Sampling of Continuous Objects: Can we Computably Generate Brownian Motions?

12.00-12.30 Ivan Adrian Koswara, Gleb Pogudin, Svetlana Selivanova and Martin Ziegler. Computational Complexity of Real Matrix Powering

12.30 Conference closing

E-mail: waac2019@theoryofcomputation.asia

• WAAC 2018: August 26–27, 2018, Fukuoka, Japan
• WAAC 2017: August 25–26, 2017, Seoul, Korea
• WAAC 2016: August 30-31, 2016, Hakodate, Japan
• WAAC 2015: August 21-22, 2015, Songdo Convensia, Incheon, Korea
• WAAC 2014: July 13-15, 2014, Okinawa Convention Center, Ginowan, Japan
• WAAC 2013: July 12-13, 2013, Kyonggi University, Suwon, Korea
• WAAC 2012: July 10-11, 2012, National Institute of Informatics, Tokyo, Japan
• WAAC 2011: July 8-9, 2011, Hanwha Resort, Busan, Korea
• WAAC 2010: July 23-24, 2010, Kanazawa Culture Hall, Kanazawa, Ishikawa, Japan
• WAAC 2009: July 4-5, 2009, Kookmin University, Seoul, Korea
• WAAC 2008: July 19-20, 2008, Fukuoka, Japan
• WAAC 2007: August 9-10, 2007, at Chonnam National University, Gwangju, Korea
• WAAC 2006: July 4-5, 2006, at Hokkaido University, Sapporo, Japan
• WAAC 2005: August 12-13, 2005, at Ewha Womans University, Seoul, Korea
• WAAC 2003: July 3-4, 2003, at Sendai City Information & Industry Plaza, Sendai, Japan
• WAAC 2001: June 28-29, 2001, at Pusan National University, Pusan, Korea
• WAAC 2000: July 21-22, 2000, at University of Tokyo, Tokyo, Japan
• WAAC 1999: July 19-20, 1999, at Seoul National University, Seoul, Korea
• WAAC 1997: July 25-26, 1997, at Kyushu University, Fukuoka, Japan
• WAAC 1996: August 23-24, 1996, at KAIST, Taejon, Korea
• WAAC 1995: July 20-21, 1995, at Osaka Electro-Communication University, Japan