Publications of 2014 Publications of 2015 Publications of 2016 Publications of 2017 Publications of 2018 Publications of 2020

A: Sublinear-time Algorithm Group (Team A)

D: Sublinear Data Structure Group (Team D)

M: Sublinear-time Modeling Group (Team M)

## Awards

A DAYPLA Award (Sponsor Special Award), Web Intelligence and Interaction Research Group, Munehiko Sasajima, 29/06/19.

D 2019 Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science and Technology Science and Technology Award (Science and Technology Promotion Division), Ministry of Education, Culture, Sports, Science and Technology, Katsutoshi Yada, 09/04/19.

D Minister of Education, Culture, Sports, Science and Technology Young Scientist Award, Ministry of Education, Culture, Sports, Science and Technology, Shin-ichi Tanigawa, 17/04/19.

D Best Paper Award, The 16th International Symposium on Algorithms and Data Structures (WADS 2019), Sankardeep Chakraborty, 07/08/19.

D IPSJ Hokkaido Branch Academic Research Award, IPSJ, Naoya Toriyabe, Isamu Furuya and Takuya Kida, 05/10/19.

D Okawa Publishing Award, Okawa Information and Communication Foundation, Kunihiko Sadakane, 30/10/19.

D Mitani Business Contest, Mitani Sangyo Co., Ltd., Shinichi Yamagiwa, 13/12/19.

M Student Encouragement Award, IPSJ, Tomu Katsumata and Muneki Yasuda, 05/03/20.

## Conferences

### Invited talks

A Kenjiro Takazawa, “b-branchings: Branchings with High Indegree”, The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2019), Tokyo, Japan, 30/05/19.

A Michael Williamson, “Validating NMR protein structures using structural rigidity theory”, Invited seminar at PDBe EBI-EMBL Wellcome Sanger Institute, Cambridge, UK, 12/06/19.

A Adnan Sljoka, “Lifting the curtain: probing biological secrets at molecular level with rigidity theory and algorithms”, 2nd International Conference on Applications of Mathematics to Nonlinear Sciences, Pokhara, Nepal, 27/06/19.

A Hiro Ito, “Sublinear-Time Paradigm — How to Challenge Big Data (Keynote Speech)”, The 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), Xiamen, China, 13/12/19.

D Katsutoshi Yada, “Sensor Marketing and Data Mining”, 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Budapest, Hungary, 05/09/19.

D Shin-ichi Nakano, “Dispersion Problems”, 2nd International Conference on Innovation in Engineering and Technology (ICIET-19), Dhaka, Bangladesh, 23/12/19.

M Shun Kataoka, “Neural network and its variants”, The 34th International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2019), Jeju, Korea, 23/06/19.

M Muneki Yasuda, “Empirical Bayes method for Boltzmann machines”, Workshop on Statistical Physics of Disordered Systems and Its Applications (SPDSA2019), Miyagi, 27/10/19.

### Oral presentations

A Y. Asahiro, G. Lin, Z. Liu and E. Miyano, “On the Approximability of the Maximum Induced Matching Problem on Regular Graphs”, The 12th Annual Meeting of the Asian Association for Algorithms and Computation, Seoul, South Korea, 19/04/19.

A Y. Higashikawa, “An Improved Algorithm for Minsum k-Sink Problems on Dynamic Flow Path Networks”, The 30th European Conference on Operational Research (EURO 2019), Dublin, Ireland, 24/06/19.

A J. Kawahara, T. Saitoh, H. Suzuki and R. Yoshinaka, “Colorful Frontier-based Search: Implicit Enumeration of Chordal and Interval Subgraphs”, Special Event on Analysis of Experimental Algorithms, Kalamata, Greece, 24/06/19.

A K. Higashizono and H. Ito, “Hyperfiniteness of hierarchical models for complex networks”, The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2019), Tokyo, Japan, 08/09/19.

A H. Ito, C. Nara, I. Shirahama and M. Tomura, “Strip flat folding with parallel oblique or orthogonal zigzag mountain-valley-assigned creases”, The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2019), Tokyo, Japan, 08/09/19.

A A. Sljoka, “Rigidity of graphs for structural protein validation and functional design”, The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, 30/10/19.

A H. Ito, “Constant-time algorithms on complex networks”, The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, 30/10/19.

A K. Chiba and H. Ito, “Sublinear progressive algoriothms — The frame work and fundamental theorems”, The 5th International Workshop on Innovative Algorithms for Big Data (IABD2019), Kyoto, Japan, 30/10/19.

A D M T. Horiyama, S. Nakano, T. Saitoh, K. Suetsugu, A. Suzuki, R. Uehara, T. Uno and K. Wasa, “Max-Min 3-dispersion Problems”, The 25th International Computing and Combinatorics Conference (COCOON 2019), Xian, China, 29/07/19.

D S. Chakraborty, “Succinct Data Structures for Families of Interval Graphs”, 17th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, Enschede, The Netherlands, 01/07/19.

D G. Hu, S. Nakano, R. Uehara and T. Uno, “Simple Fold and Cut Problem for Line Segments”, The 31st Canadian Conference in Computational Geometry, Edmonton, Alberta, Canada, 08/08/19.

D K. Ishibashi and K. Yada, “Analysis of social influence on in-store purchase behavior by using ecological system of ants”, 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Budapest, Hungary, 05/09/19.

D K. Yada and H. Gu, “The impact of self-control on search behavior”, 23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, Budapest, Hungary, 05/09/19.

D K. Ishibashi, “Application of Deep Learning to Pre-processing of Cousumer’s Eye Tracking Data in Supermarket”, 2019 International Conference on Data Mining Workshops, Beijing, China, 08/11/19.

D K. Ishibashi, C. Xiao and K. Yada, “Study of the Effects of Visual Complexity and Consumer Experience on Visual Attention and Purchase Behavior through the Use of Eye Tracking”, 2019 IEEE International Conference on Big Data, Los Angels, USA, 09/12/19.

M A. Shioura, “M-convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Re-allocation in Bike Sharing System”, 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan, 28/05/19.

M A. Shioura, “Connection Between Discrete Convex Analysis and Auction Theory”, SIAM Conference on Applied Algebraic Geometry, Bern, Switzerland, 09/07/19.

M A. Suzuki, “Diameter of colorings under Kempe changes”, The 25th International Computing and Combinatorics Conference (COCOON 2019), Xian, China, 30/07/19.

M T. Ito, “Shortest Reconfiguration of Perfect Matchings via Alternating Cycles”, The 27th Annual European Symposium on Algorithms (ESA 2019), Munich, Germany, 09/09/19.

M M.J. Miyama and A.S. Koshikawa, “No Chain Embedding on Quantum Annealer and its Perspective”, D-Wave Qubits North America Users Conference 2019, Newport, USA, 26/09/19.

M S. Arai, “Statistical mechanical analysis of reverse annealing for code-division multiple-access multiuser demodulator”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2019) Statistical-Mechanical Informatics and Statistical Machine Learning Theory in Big Data Sciences, Miyagi, Japan, 27/10/19.

M A.S. Koshikawa, “Search for the ground state of a spin glass with Bayesian optimization”, Statistical Physics of Disordered Systems and Its Applications (SPDSA2019) Statistical-Mechanical Informatics and Statistical Machine Learning Theory in Big Data Sciences, Miyagi, Japan, 27/10/19.

### Poster presentations

A N. Fowler, A. Sljoka and M. Williamson, “Validation of NMR protein structures using structural rigidity theory and random coil index”, The 18th European Conference on Computational Biology, Basel, Switzerland, 22/07/19.

A A. Sljoka, “Detection of Allosteric Pathways and Hotspots with Rigidity Propagation across GPCR networks”, GPCR Workshop, Hawaii, USA, 01/12/19.

A M. Williamson, “Is your NMR protein structure accurate? We have the ANSURR!”, Reson8 5th Biophysical and biochemical symposium, York, USA, 10/01/20.

A M. Huai, D. Wang, C. Miao, J. Xu and A. Zhang, “Pairwise Learning with Differ- ential Privacy Guarantees”, AAAI2020, New York, USA, 09/02/20.

D S. Yamagiwa, R. Morita and K. Marumo, “Reducing Symbol Search Overhead on Stream-based Lossless Data Compression”, ICCS 2019, Faro, Portugal, 13/06/19.

D Y.Z. Zhang, A. Akdemir, G. Tremmel, S. Imoto, S. Miyano, T. Shibuya and R. Yamaguchi, “Nanopore base-calling from a perspective of instance segmentation”, The 18th European Conference on Computational Biology, Basel, Switzerland, 21/07/19.

D S. Yamagiwa, E. Hayakawa and K. Marumo, “Adaptive Stream-based Entropy Coding”, Data Compression Conference 2020, Snowbird, Utah, USA, 24/03/20.

M M. Okuyama and M. Ohzeki, “An exact solution of the partition function for mean-field quantum spin systems without the static approximation”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M S. Arai, M. Ohzeki and K. Tanaka, “Mean-field analysis of quantum error-correcting codes with non-stoquastic Hamiltonian”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M C. Takahashi, M. Ohzeki and K. Tanaka, “Statistical-mechanical analysis of restrictecd Boltzmann machine with transverse field”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 226/06/19.

M A. Koshikawa, M. Ohzeki and K. Tanaka, “Black-box optimization with D-Wave 2000Q”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M N. Maruyama, M. Ohzeki and K. Tanaka, “Optimization of bus schedule using quantum annealer”, Adiabatic Quantum Computing Conference 2019, Innsbruck, Austria, 26/06/19.

M H. Naganuma, D. Hendrian, R. Yoshinaka, A. Shinohara and N. Kobayashi, “Grammar Compression with Probabilistic Context-Free Grammar”, Data Compression Conference 2020, Snowbird, Utah, USA, 24/03/20.

## Journal papers

A H.L. Bodlaender, T. Hanaka, Y. Okamoto, Y. Otachi and T.C. van der Zanden, “Subgraph Isomorphism on Graph Classes that Exclude a Substructure”, Proceedings of 11th International Conference on Algorithms and Complexity (CIAC 2019), pp.87-98, 2019 (DOI: 10.1007/978-3-030-17402-6_8)

A Y. Asahiro, J. Jansson, E. Miyano, H. Ono and T.P. Sandhya, “Graph orientation with edge modifications”, Proceedings of FAW 2019, Vol.11458, pp.38-50, 2019 (DOI: 10.1007/978-3-030-18126-0_4)

A Y. Asahiro, T. Kubo and E. Miyano, “Experimental evaluation of approximation and heuristic algorithms for maximum distance-bounded subgraph problems”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.143-161, 2019 (DOI: 10.1007/s12626-019-00036-2)

A R. Yamamoto and A. Takizawa, “Partitioning Vertical Evacuation Areas in Umeda Underground Mall to Minimize the Evacuation Completion Time”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.209-225, 2019 (DOI: 10.1007/s12626-019-00037-0)

A E. Boros, K.M. Elbassioni, V. Gurvich and K. Makino, “A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions,” Inf. Comput. No.267, pp.74-95, 2019 (DOI: 10.1016/j.ic.2019.03.005)

A E. Boros, V. Gurvich, N.B. Ho, K. Makino and P. Mursic, “Sprague-Grundy function of symmetric hypergraphs,” Journal of Combinatorial Theory, Series A, No.165, pp.176-186, 2019 (DOI: 10.1016/j.jcta.2019.02.006)

A K. Takazawa and Y. Yokoi, “A generalized-polymatroid approach to disjoint common independent sets in two matroids”, Discrete Mathematics, Vol.342, issue 7, pp.2002-2011, 2019 (DOI: 10.1016/j.disc.2019.03.009)

A D. Wang, C. Chen and J. Xu, “Differentially Private Empirical Risk Minimization with Non-convex Loss Functions”, Proc. the 36th International Conference on Machine Learning (ICML 2019), pp.6326-6535, 2019.

A P. Mehrabi, C.D. Pietrantonio, T.H. Kim, A. Sljoka, K. Taverner, C. Ing, N. Kruglyak, R. Pomès, E.F. Pai and R.S. Prosser, “Substrate-Based Allosteric Regulation of a Homodimeric Enzyme”, J. Am. Chem. Soc., Vol.141, No.29, 11540-11556, 2019 (DOI: 10.1021/jacs.9b03703)

A Y. Kobayashi, Y. Kobayashi, S. Miyazaki and S. Tamaki, “An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number”, IWOCA 2019, Lecture Notes in Computer Science, Vol.11638, pp.327-338, 2019 (DOI: 10.1007/978-3-030-25005-8)

A Y. Kawase, X. Han and K. Makino, “Proportional cost buyback problem with weight bounds”, Theoretical Computer Science, No.774, pp.51-64, 2019 (DOI: 10.1016/j.tcs.2016.06.005)

A H. Hayakawa, T. Ishii, H. Ono and Y. Uno, “Settlement fund circulation problem”, Discrete Applied Mathematics, Vol.265, pp.86-103, 2019 (DOI: 10.1016/j.dam.2019.03.017)

A E.D. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara and Y. Uno, “Reconfiguring Undirected Paths”, Lecture Notes in Computer Science, Vol.11646, pp.353-365, 2019 (DOI: 10.1007/978-3-030-24766-9_26)

A Y. Kawase, X. Han and K. Makino, “Unit Cost Buyback Problem,” Theory Comput. Syst. Vol.63, No.6, pp.1185-1206, 2019 (DOI: 10.1007/s00224-018-9897-7)

A D. Wang and J. Xu, “Principal Component Analysis in the Local Differential Privacy Model”, Proc. 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), pp.4795-4801, 2019 (DOI: 10.24963/ijcai.2019/66)

A Y. Asahiro, G. Lin, Z. Liu and E. Miyano, “An approximation algorithm for the maximum induced matching problem on C_5-free regular grapha”, IEICE TRANSACTIONS on Information and Systems, Vol.E102-A, No.9, pp.1142-1149, 2019 (DOI: 10.1587/transfun.E102.A.1142)

A H. Ito, A. Nagao and T. Park, “Generalized Shogi, Chess, and Xiangqi are Constant-Time Testable”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. 102, No.9, pp.1126-1133, 2019 (DOI: 10.1587/transfun.E102.A.1126)

A Y. Higashikawa and N. Katoh, “A Survey on Facility Location Problems in Dynamic Flow Networks”, The Review of Socionetwork Strategies, Vol.13, pp.163-208, 2019 (DOI: 10.1007/s12626-019-00047-z)

A Y. Honda, Y. Inoue, H. Ito, M. Sasajima, J. Teruyama and Y. Uno, “Hyperfiniteness of Real-world Networks”, The Review of Socionetwork Strategies, Vol.13, pp.123-141, 2019 (DOI: 10.1007/s12626-019-00051-3)

A K. Elbassioni and K. Makino, “Oracle-based Primal-dual Algorithms for Packing and Covering Semidefinite Programs”, The 27th Annual European Symposium on Algorithms (ESA 2019), 2019 (DOI: 10.4230/LIPIcs.ESA.2019.43)

A E. Demaine, H. Ito, S. Langerman, J. Lynch, M. Rudoy and K. Xiao, “Cookie Clicker”, Graphs and Combinatorics, Vol.36, pp.269-302, 2020 (DOI: 10.1007/s00373-019-02093-4)

A H. Ito, “What graph properties are constant-time testable? -Dense graphs, sparse graphs, and complex networks”, The Review of Socionetwork Strategies, Vol.13, pp.101-121, 2019 (DOI: 10.1007/s12626-019-00054-0)

A X. Han, Q. Chen and K. Makino, “Online knapsack problem under concave functions”, Theoretical Computer Science Vol.786, pp.88-95, 2019 (DOI: 10.1016/j.tcs.2018.03.025)

A D. Wang and J. Xu, “Faster constrained linear regression via two-step preconditioning”, Neurocomputing, Vol.364, pp.280-296, 2019 (DOI: 10.1016/j.neucom.2019.07.070 )

A T. Sakai, K. Seto, S. Tamaki and J. Teruyama,“Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression”, J. Comput. Syst. Sci., Vol.105, pp.87-103, 2019 (DOI: 10.1016/j.jcss.2019.04.004)

A Y. Asahiro, J. Jansson, G. Lin, E. Miyano, H. Ono and T. Utashima, “Exact algorithms for the bounded repetition longest common subsequence problem”, Proc. 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), LNCS11949, pp.1-12, 2019 (DOI: 10.1007/978-3-030-36412-0_1)

A X. Han, Y. Kawase, K. Makino and H. Yokomaku, “Online Knapsack Problems with a Resource Buffer”, ISAAC 2019: 28:1-28:14 2019 (DOI: 10.4230/LIPIcs.ISAAC.2019.28)

A O. Aichholzer, M. Korman, Y. Okamoto, I. Parada, D. Perz, A.van Renssen and B. Vogtenhuber, “Graphs with Large Total Angular Resolution”, Proceedings of 27th International Symposium on Graph Drawing and Network Visualization，pp.193-199, 2019 (DOI: 10.1007/978-3-030-35802-0_15)

A Y. Okamoto, A. Ravsky and A. Wolff, “Variants of the Segment Number of a Graph”, Proceedings of 27th International Symposium on Graph Drawing and Network Visualization, pp.430-443, 2019 (DOI: 10.1007/978-3-030-35802-0_33)

A Z. Huang, Q. Feng, J. Wang and J. Xu, “Small Candidate Set for Translational Pattern Search”, Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), pp.16:1-26:17, 2019 (DOI: 10.4230/LIPIcs.ISAAC.2019.26)

A E. Boros, V. Gurvich, N.B. Ho, K. Makino and P. Mursic, “Sprague-Grundy function of matroids and related hypergraphs”, Theor. Comput. Sci., Vol.799, pp.40-58, 2019 (DOI: 10.1016/j.tcs.2019.09.041)

A P. Carmi, M.K. Chiu, M.J. Katz, M. Korman, Y. Okamoto, A.van Renssen, M. Roeloffzen, T. Shiitada and S. Smorodinsky, “Balanced line separators of unit disk graphs”, Computational Geometry: Theory and Applications, Vol.86, 2019 (DOI: 10.1016/j.comgeo.2019.101575)

A H. Ito, A. Khoury and I. Newman, “On the characterization of 1-sided error strongly-testable graph properties for bounded-degree graphs”, Journal of Computational Complexity, Vol.29, No.1, pp.1-45, 2020 (DOI: 10.1007/s00037-020-00191-6)

A K. Yamazaki, T. Saitoh, M. Kiyomi and R. Uehara, “Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs”, Theoretical Computer Science, Vol.806, pp.310-322, 2020 (DOI: 10.1016/j.tcs.2019.04.017)

A K. Iwama and J. Teruyama, “Improved Average Complexity for Comparison-based Sorting”, Theoretical Computer Science, Vol.807, pp.201-219, 2019 (DOI: 10.1016/j.tcs.2019.06.032)

A B. Soumen, A. Sljoka and C. Amit, “Allosteric regulation of Glutamate dehydrogenase deamination activity”, Scientific Reports, 2020 (DOI: 10.1016/j.bpj.2019.11.2851)

A Y. Asahiro, H. Eto, T. Hanaka, G. Lin, E. Miyano and I. Terabaru, “Parameterized algorithms for the happy set problem”, Proc. 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), LNCS12049, pp.323-328, 2020 (DOI: 10.1007/978-3-030-39881-1_27)

A Y. Kawase and K. Makino, “Surrogate optimization for p-norms”, Discret. Optim. 34, 2019 (DOI: 10.1016/j.disopt.2019.05.003)

A R. Mubasher, B. Soumen, A. Sljoka and A. Chakraborty, “Feedforward Control of Plant Nitrate Transporter NRT1.1Biphasic Adaptive Activity”, Biophysical Journal, Vol.118, No.4, pp.898-908, 2019 (DOI: 10.1016/j.bpj.2019.10.018)

A Z. Huang and J. Xu, “An Efficient Sum Query Algorithm for Distance-Based Locally Dominating Functions”, Algorithmica, 2020 (DOI: 10.1007/s00453-020-00691-w)

A R. Benkoczi, B. Bhattacharya, Y. Higashikawa, T. Kameda and N. Katoh, “Minsum k-sink problem on path networks”, Theor. Comput. Sci. 806: 388-401, 2020 (DOI: 10.1016/j.tcs.2019.05.047)

A D. Wang and J. Xu, “Tight Lower Bound of Sparse Covariance Matrix Estimation in the Local Differential Privacy Model”, Theoretical Computer Science, Vol.815, pp.47-59, 2020 (accepted) (DOI: 10.1016/j.tcs.2020.02.02)

A H. Ding and J. Xu, “Learning the Truth Vector in High Dimensions”, Journal of Computer and System Sciences, 109:78-94, 2020 (accepted) (DOI: 10.1016/j.jcss.2019.12.002)

A X. Wang, A. Mafi, A. Sljoka, W.A. Goddard and Y. Libin, “Conformational Insights into Signaling Mechanism of Partial Agonism in GPCRs”, Cell (submitted)

A D M T. Horiyama, S. Nakano, T. Saitoh, K. Suetsugu, A. Suzuki, R. Uehara, T. Uno and K. Wasa, “Max-Min 3-dispersion Problems”, Proc. of COCOON 2019, LNCS 11653, pp.291-300, 2019 (DOI: 10.1007/978-3-030-26176-4_24)

A M T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Shortest Reconfiguration of Perfect Matchings via Alternating Cycles,” Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics, Vol.144, pp.61:1-61:15, 2019 (DOI: 10.4230/LIPIcs.ESA.2019.61)

A M J. Kawahara, T. Saitoh, H. Suzuki and R. Yoshinaka, “Colorful Frontier-based Search: Implicit Enumeration of Chordal and Interval Subgraphs,” Special Event on Analysis of Experimental Algorithms, LNCS, Vol.11544, pp.125-141, 2019 (DOI: 10.1007/978-3-030-34029-2_9)

D T. Jordan and S. Tanigawa, “Global rigidity of triangulations with braces”, Journal of Combinatorial Theory, Series B, No.136, pp.249-288, 2019 (DOI: 10.1016/j.jctb.2018.11.003)

D H. Furuta, K. Ishibashi and K. Nakatsu, “Resilient restoration scheduling on road network,” Proceedings of 13th International Conference on Applications of Statistics and Probability in Civil Engineering(ICASP13), pp.1–8, 2019 (DOI: 10.22725/ICASP13.141)

D S. Yamagiwa, R. Morita and K. Marumo, “Reducing Symbol Search Overhead on Stream-based Lossless Data Compression”, Proceedings of ICCS 2019, LNCS 11540, pp.619-626, 2019 (DOI: 10.1007/978-3-030-22750-0_59)

D S. Chakraborty, A. Mukherjee and S.R. Satti, “Space Efficient Algorithms for Breadth-Depth Search”, Fundamentals of Computation Theory – 22nd International Symposium (FCT 2019), pp.201-212, 2019 (DOI: 10.1007/978-3-030-25027-0_14)

D H. Acan, S. Chakraborty, S. Jo and S.R. Satti, “Succinct Data Structures for Families of Interval Graphs”, Workshop on Algorithms and Data Structures (WADS 2019), pp.1-13, 2019 (DOI: 10.1007/978-3-030-24766-9_1)

D S. Denzumi, “New Algorithms for Manipulating Sequence BDDs”, The 24th International Conference on Implementation and Application of Automata (CIAA 2019), pp.108-120, 2019 (DOI: 10.1007/978-3-030-23679-3_9)

D S. Ahmed, S. Nakano and Md.S. Rahman, “One-dimensional r-Gathering under Uncertainty”, Proc. of AAIM 2019, LNCS 11640, pp.1-15, 2019 (DOI: 10.1007/978-3-030-27195-4_1)

D I. Furuya and T. Kida, “Compaction of Church Numerals”, Algorithms, Vol.12, No.8:159, 2019 (DOI: 10.3390/a12080159)

D A. Akdemir and T. Gungor, “A Detailed Analysis and Improvement of Feature-Based Named Entity Recognition for Turkish”, SPECOM 2019, LNAI 11658, pp.9–19, 2019 (DOI: 10.1007/978-3-030-26061-3_2)

D S. Chakraborty and K. Sadakane, “Indexing Graph Search Trees and Applications”, Proceedings of MFCS, LIPIcs 138, pp.67:1-67:14, 2019 (DOI: 10.4230/LIPIcs.MFCS.2019.67)

D K. Yamanaka, Y. Matsui and S. Nakano, “Enumerating Highly-Edge-Connected Spanning Subgraphs”, IEICE TRANS. FUNDAMENTALS, Vol.E102-A, No.9, pp.1002-1006, 2019 (DOI: 10.1587/transfun.E102.A.1002)

D Y. Sasaki, T. Shibuya, K. Ito and H. Arimura, “Efficient Approximate 3-Dimensional Point Set Matching Using Root-Mean-Square Deviation Score”, IEICE Transactions on Fundamentals, E102.A(9), pp.1159-1170, 2019 (DOI: 10.1587/transfun.E102.A.986)

D M.J. Kashyop, T. Nagayama and K. Sadakane, “Faster algorithms for shortest path and network flow based on graph decomposition”, Journal of Graph Algorithms and Applications, Vol.23, No.5, pp.781-813, 2019 (DOI: 10.7155/jgaa.00512)

D S. Nakano, “A Simple Algorithm for r-gatherings on the Line”, JGAA, Vol.23, No.5, pp.837-845, 2019 (DOI: 10.7155/jgaa.00514)

D T. Gagie, T. I, G. Manzini, G. Navarro, H. Sakamoto and Y. Takabatake, “Rpair: Rescaling RePair with Rsync”, SPIRE 2019, pp.35-44, 2019 (DOI: 10.1007/978-3-030-32686-9_3)

D T. Shibuya, “Application-Oriented Succinct Data Structures for Big Data”, The Review of Socionetwork Strategies, Vol.13, pp.227–236, 2019 (DOI: 10.1007/s12626-019-00045-1)

D K. Sumigawa and K. Sadakane, “Storing Partitions of Integers in Sublinear Space”, The Review of Socionetwork Strategies, Vol.13, pp.237–252, 2019 (DOI: 10.1007/s12626-019-00044-2)

D K. Ishibashi and K. Yada, “Analysis of social influence on in-store purchase behavior by using ecological system of ants”, Procedia Computer Science, Vol.159, pp.2162-2171, 2019 (DOI: 10.1016/j.procs.2019.09.390)

D K. Ishibashi, “Application of Deep Learning to Pre-processing of Cousumer’s Eye Tracking Data in Supermarket”, Proceedings of 2019 International Conference on Data Mining Workshops (ICDMW), pp.341-348, 2019 (DOI: 10.1109/ICDMW.2019.00057)

D K. Ishibashi, C. Xiao and K. Yada, “Study of the Effects of Visual Complexity and Consumer Experience on Visual Attention and Purchase Behavior through the Use of Eye Tracking”, Proceedings of 2019 IEEE International Conference on Big Data (Big Data), pp.2664-2673, 2019 (DOI: 10.1109/BigData47090.2019.9005498)

D T. Araki and S. Nakano, “Max-Min Dispersion on a Line”, Journal of Combinatorial Optimization, 2020 (DOI: 10.1007/s10878-020-00549-5)

D K. Amano and S. Nakano, “An Approximation Algorithm for the 2-dispersion Problem”, IEICE TRANS. INF.& SYST., Vol.E103-D, No.3, pp.506-508, 2020 (DOI: 10.1587/transinf.2019FCP0005)

D Y. Yoshimoto, M. Kataoka, Y. Takabatake, T. I, K. Shin and H. Sakamoto, “Faster Privacy-Preserving Computation of Edit Distance with Moves”, WALCOM 2020, pp.308-320, 2020 (DOI: 10.1007/978-3-030-39881-1_26)

D S. Chakraborty and K. Sadakane, “Indexing Graph Search Trees and Applications”, Proceedings of MFCS, 2019 (in press)

D I. Furuya, “Practical Repetition-Aware Grammar Compression”, In Proceedings of Data Compression Conference, 2020 (in press)

M M. Yasuda, H. Sakata, S.I. Cho, T. Harada, A. Tanaka and M. Yokoyama, “An efficient test method for noise robustness of deep neural networks”, Nonlinear Theory and its Applications (NOLTA), IEICE, Vol.10, Issue 2, pp.221-235, 2019 (DOI: 10.1587/nolta.10.221)

M T. Ito, N. Kamiyama, Y. Kobayashi and Y. Okamoto, “Algorithms for Gerrymandering Over Graphs”, Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), pp.1413-1421, 2019 (DOI: 10.5555/3306127.3331851)

M T. Ito and Y. Otachi, “Reconfiguration of Colorable Sets in Classes of Perfect Graphs”, Theoretical Computer Science, Vol.772, pp.111-122, 2019 (DOI: 10.1016/j.tcs.2018.11.024)

M S. Kataoka and M. Yasuda, “Bayesian Image Denoising with Multiple Noisy Images”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.267-280, 2019 (DOI: 10.1007/s12626-019-00043-3)

M M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki and K. Wasa, “Diameter of colorings under Kempe changes”, Proceedings of COCOON 2019, Vol.11653, pp.52-64, 2019 (DOI: 10.1007/978-3-030-26176-4_5)

M T. Ito, H. Mizuta, N. Nishimura and A. Suzuki, “Incremental optimization of independent sets under the reconfiguration framework”, Proceedings of COCOON 2019, Vol.11653, pp.313-324, 2019 (DOI: 10.1007/978-3-030-26176-4_26)

M Y. Yokoyama, T. Katsumata and M. Yasuda, “Restricted Boltzmann Machine with Multivalued Hidden Variables: a model suppressing over-fitting”, The Review of Socionetwork Strategies, Vol.13, No.2, pp.253-266, 2019 (DOI: 10.1007/s12626-019-00042-4)

M N. Minamikawa and A. Shioura, “Separable convex resource allocation problem with L1-distance constraint”, Journal of Operations Research Society of Japan, Vol.62, pp.109-120, 2019 (DOI: 10.15807/jorsj.62.109)

M S. Kobayashi, D. Hendrian, R. Yoshinaka and A. Shinohara, “An improvement of the Franek-Jennings-Smyth pattern matching algorithm”, Proceedings of Prague Stringology Conference 2019, pp.56-68, 2019.

M M. Bonamy, N. Bousquet, M. Heinrich, T. Ito, Y. Kobayashi, A. Mary, M. Mühlenthaler and K. Wasa, “The Perfect Matching Reconfiguration Problem”, Proceedings of MFCS 2019, Vol.138, pp.80:1-80:14, 2019 (DOI: 10.4230/LIPIcs.MFCS.2019.80)

M H. Mizuta, T. Hatanaka, T. Ito and X. Zhou, “Reconfiguration of Minimum Steiner Trees via Vertex Exchanges”, Proceedings of MFCS 2019, Vol.138, pp.79:1-79:11, 2019 (DOI: 10.4230/LIPIcs.MFCS.2019.79)

M K. Chubachi, D. Hendrian, R. Yoshinaka and A. Shinohara, “Query Learning Algorithm for Residual Symbolic Finite Automata”, In Proceedings of the Tenth International Symposium on Games, Automata, Logics, and Formal Verification, 2019.

M M. Yasuda, K. Katou, Y. Mikuni, Y. Yokoyama, T. Harada, A. Tanaka and M. Yokoyama, “Detection of human-interaction network using Markov random field”, Nonlinear Theory and its Applications (NOLTA), IEICE, Vol.10, Issue 4, pp.485-495, 2019 (DOI: 10.1587/nolta.10.485)

M M. Tsuchiya, A. Tanaka, M. Yasuda, T. Harada, S. Cho and M. Yokoyama, “Estimation of Sleep Onset and Awaking Time Using a Deep Neural Network with Physiological Data during Sleep”, Nonlinear Theory and its Applications (NOLTA), IEICE, Vol.10, Issue 4, pp.366-372, 2019 (DOI: 10.1587/nolta.10.366)

M M. Yasuda and S. Ueno, “Improvement of Batch Normalization in Imbalanced Data”, Proceedings of the 2019 International Symposium on Nonlinear Theory and its Applications (NOLTA2019), pp.146-149, 2019.

M S. Cho, M. Tsuchiya, A. Tanaka, M. Yasuda, T. Harada and M. Yokoyama, “A Study on the Relation Between the Estimated Sleep Satisfaction Levels Using Multiple Regression Analysis and Autonomic Nervous System”, Proceedings of the 2019 International Symposium on Nonlinear Theory and its Applications (NOLTA2019), pp.153-156, 2019.

M A. Tanaka, S. Nagasawa, M. Yasuda, T. Harada and M. Yokoyama, “Overcoming Chasm Phenomena in Diffusion on Cookpad Community”, Proceedings of the 2019 International Symposium on Nonlinear Theory and its Applications (NOLTA2019), pp.150-152, 2019.

M M. Yasuda and T. Obuchi, “Empirical Bayes Method for Boltzmann Machines”, Journal of Physics A: Mathematical and Theoretical, Vol.53, No.1, 2019 (DOI: 10.1088/1751-8121/ab57a7)

M K. Nakashima, D. Hendrian, R. Yoshinaka and A. Shinohara, “An Extension of Linear-size Suffix Tries for Parameterized Strings”, SOFSEM (Doctoral Student Research Forum) 2020: 97-108, 2020.

M D. Jargalsaikhan, D. Hendrian, R. Yoshinaka and A. Shinohara, “Parallel Duel-and-Sweep Algorithm for the Order-Preserving Pattern Matching,” SOFSEM 2020, pp.211-222, 2020.

M T. Hanaka, T. Ito, H. Mizuta, B. Moore, N. Nishimura, V. Subramanya, A. Suzuki and K. Vaidyanathan, “Reconfiguring Spanning and Induced Subgraphs,” Theoretical Computer Science, Vol.806, pp.553-566, 2020 (DOI: 10.1016/j.tcs.2019.09.018)

M Y. Tamura, T. Ito and X. Zhou, “Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs,” Proceedings of the 14th International Conference and Workshop on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science, Vol.12049, pp.286-295, 2020 (DOI: 10.1007/978-3-030-39881-1_24)

M K. Kimura and A. Suzuki, “Trichotomy for the reconfiguration problem of integer linear systems,” Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science, Vol.12049, pp.336-341, 2020 (DOI: 10.1007/978-3-030-39881-1_29)

M D.A. Hoang, A. Suzuki and T. Yagita, “Reconfiguring k-path vertex covers,” Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science, Vol.12049, pp.133-145, 2020 (DOI: 10.1007/978-3-030-39881-1_12)

M M. Bonamy, M. Heinrich, T. Ito, Y. Kobayashi, H. Mizuta, M. Mühlenthaler, A. Suzuki and K. Wasa, “Shortest Reconfiguration of Colorings Under Kempe Changes,” Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Leibniz International Proceedings in Informatics, Vol.154, pp.35:1-35:14, 2020 (DOI: 10.4230/LIPIcs.STACS.2020.35)

M S. Narisada, D. Hendrian, R. Yoshinaka and A. Shinohara, “Linear-time online algorithm for inferring the shortest path graph from a walk label”, Theor. Comput. Sci., Vol.812, pp.187-202, 2020 (in press) (DOI: 10.1016/j.tcs.2019.10.029)

M A. Blanché, P. Ouvrard, H. Mizuta and A. Suzuki, “Decremental optimization of dominating sets under the reconfiguration framework”, Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), to appear (accepted)

M M. Okuyama and M. Ohzeki, “Inequality for local energy of Ising models with quenched randomness and its application”, arXiv::2001.10707 (submitted)