Publication List of Eiji Miyano
Publication List
Kyutech Algorithms Group members / Downloadable documents from Kyutacar
Refereed papers in journals, book series, and international conferences
20xx
Mingyang Gong, Jiang Fan, Guohui Lin, Eiji Miyano. Approximation algorithms for covering vertices by long paths. Algorithmica. Accepted.
2024
Yuichi Asahiro, Jepser Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima. Polynomial-time equivalences and refined algorithms for longest common subsequence variants. Discrete Applied Mathematics. Vol. 353, pp.44-64 (August 15, 2024). DOI:10.1016/j.dam.2024.04.006
Hiroshi Eto, Shunsuke Kawaharada, Guohui Lin, Eiji Miyano, Tugce Ozdemir. Directed path partition problems on directed acyclic graphs. IWOCA 2024, Ischia, Italy (July 1 -3, 2024). Accepted.
Mingyang Gong, Guohui Lin, Eiji Miyano, Bing Su, Weitian Tong. A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow shops. Annals of Operations Research. Vol. 335, pp.185-204 (February 19, 2024). DOI:10.1007/s10479-024-05860-6
2023
Yuichi Asahiro, Jesper Jansson, Avraham A. Melkman, Eiji Miyano, Hirotaka Ono, Quan Xue, and Shay Zakove. Shortest longest-path graph orientations (preliminary version). The 29th Annual International Computing and Combinatorics Conference (COCOON 203), LNCS14422, pp.141-154, Hawaii, USA (December 15-17, 2023). DOI: 10.1007/978-3-031-49190-0_10
Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita.Path cover problems with length cost. Algorithmica, Vol.85, Issue 11, pp.3348-3375 (November, 2023). DOI:10.1007/s00453-023-01106-2
Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura. Happy set problem on subclasses of co-comparability graphs. Algorithmica, Vol.85, Issue 11, pp.3327-3347 (November, 2023). DOI:10.1007/s00453-022-01081-0
Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru. Corrigendum to ``Complexity and approximability of the happy set problem'' [Theoret. Comput. Sci. 866(2021) 123--144]. Theoretical Computer Science, Vol. 975, Article 114114 (13 pages) (October 9, 2023). DOI:10.1016/j.tcs.2023.114114
Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu. On computing a center persistence diagram. 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), LNCS 14292, pp.262-275, Universitat Trier, Trier, Germany (September 18-21, 2003). DOI:10.1007/978-3-031-43587-4_19
Yuichi Asahiro, Hiroshi Eto, Jepser Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Shunichi Tanaka. Approximation algorithms for the longest run subsequence problem (preliminary version). 34th Annual Symposium on Combinatorial Pattern Matching (CPM2023), LIPIcs 259, Article No.2, pp.2:1-2:12, Lecture hall Maurice Gross in the building Copernic, located in the middle of the Descartes campus of the Université Gustave Eiffel, Marne-la-Vallée, France (June 26-28, 2023). DOI:10.4230/LIPIcs.CPM.2023.2
Yuichi Asahiro, Hiroshi Eto, Kana Korenaga, Guohui Lin, Eiji Miyano, Reo Nonoue. Independent set under a change constraint from an initial solution (preliminary version). 13th International Conference on Algorithms and Complexity (CIAC2023), LNCS 13898, pp. 37-51, Lordos Beach Hotel, Larnaca, Cyprus (June 14-16, 2023). DOI:10.1007/978-3-031-30448-4_4
2022
Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano.Approximability of the distance independent set problem on regular graphs and planar graphs. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E105-A, No.9, pp.1211-1222 (September 1, 2022). DOI:10.1587/transfun.2021DMP0017
Mingyang Gong, Jiang Fan, Guohui Lin, Eiji Miyano. Approximation algorithms for covering vertices by long paths (preliminary version). Proc. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), LIPIcs 241, Article No.53, pp.53:1-53:14, Freihaus building of TU Wien, Vienna, Austria (August 22-26, 2022). DOI:10.4230/LIPIcs.MFCS.2022.53
Mingyang Gong, Randy Goebel, Guohui Lin, Eiji Miyano. Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing. Journal of Combinatorial Optimization, Vol.44, Issue 1, pp.877-893 (August, 2022). DOI:10.1007/s10878-022-00865-y
Yuichi Asahiro, Jepser Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima. Polynomial-time equivalences and refined algorithms for longest common subsequence variants (preliminary version). Proc. 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022), LIPIcs 223, Article No.15, pp.15:1-15:17, Faculty of Civil Engineering, Czech Technical University in Prague, Czech Republic (June 27-29, 2022). DOI:10.4230/LIPIcs.CPM.2022.15
Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita. Path cover problems with length cost (preliminary version). Proc. the 16th International Conference and Workshops on Algorithms and Computation (WALCOM2022), LNCS 13174, pp.396-408, Universitas Jember, Jember, Indonesia (March 24-26, 2022). DOI:10.1007/978-3-030-96731-4_32
Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura. Happy set problem on subclasses of co-comparability graphs (preliminary version). Proc. the 16th International Conference and Workshops on Algorithms and Computation (WALCOM2022), LNCS 13174, pp.149-160, Universitas Jember, Jember, Indonesia (March 24-26, 2022). DOI:10.1007/978-3-030-96731-4_13
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono.Upper and lower degree-constrained graph orientation with minimum penalty. Theoretical Computer Science, Vol.900, pp.53-78 (January 8, 2022). DOI:10.1016/j.tcs.2021.11.019
2021
Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru. Parameterized algorithms for the happy set problem. Discrete Applied Mathematics, Vol.304, pp.32-44 (December 15, 2021). DOI:10.1016/j.dam.2021.07.005
Qiaojun Shu, Yong Chen, Shuguang Han, Guohui Lin, Eiji Miyano, An Zhang. Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles. Theoretical Computer Science, Vol.882, pp.77-108 (August 23, 2021). DOI:10.1016/j.tcs.2021.06.017
Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru. Complexity and Approximability of the Happy Set Problem. Theoretical Computer Science, Vol.866, pp.123-144 (April 18, 2021). DOI:10.1016/j.tcs.2021.03.023
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Sandhya T.P.. Graph Orientation with Edge Modifications. International Journal of Foundations of Computer Science, Vol.322, No.2, pp.209-233 (January 30, 2021). DOI:10.1142/S012905412150012X
Yuichi Asahiro, Tetsuya Furukawa, Keiichi Ikegami, Eiji Miyano, Tsuyoshi Yagita. How to Pack Directed Acyclic Graphs into Small Blocks. Discrete Applied Mathematics, Vol.228, pp.91-113 (January 15, 2021). DOI:10.1016/j.dam.2020.08.005
2020
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hesam Nikpey, Hirotaka Ono. Graph orientation with splits. Theoretical Computer Science, Vol.844, pp.16-25 (December 6, 2020). DOI:10.1016/j.tcs.2020.07.013
Yuichi Asahiro, Jepser Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima. Exact algorithms for the repetition-bounded longest common subsequence problem. Theoretical Computer Science, Vol.838, pp.238-249 (October 24, 2020). DOI:10.1016/j.tcs.2020.07.042
Qiaojun Shu, Yong Chen, Shuguang Han, Guohui Lin, Eiji Miyano, An Zhang. Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles (preliminary version). Proc. 16th Annual Conference on Theory and Applications of Models of Computation (TAMC2020), LNCS12337, pp.426-438, Changsha, China (October 18 – October 20, 2020). DOI:10.1007/978-3-030-59267-7_36
Eiji Miyano, Toshiki Saitoh, Ryuhei Uehara, Tsuyoshi Yagita, and Tom C. van der Zanden. Complexity of the maximum k-path vertex cover problem. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E103-A, No.10, pp.1193-1201 (October 1, 2020). DOI:10.1587/transfun.2019DMP0014
Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru. Graph classes and approximability of the happy set problem (preliminary version). Proc. 16th International Computing and Combinatorics Conference (COCOON 2020), LNCS12273, pp.335-346, Georgia State University, Atlanta, GA, USA (Fully Online, August 29 – August 31, 2020). DOI:10.1007/978-3-030-58150-3_27
Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru. Parameterized algorithms for the happy set problem (preliminary version). Proc. 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), LNCS12049, pp.323-328, Institute for Mathematical Sciences, National University of Singapore (March 31 – April 2, 2020). DOI:10.1007/978-3-030-39881-1_27
2019
Yuichi Asahiro, Jepser Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima. Exact algorithms for the bounded repetition longest common subsequence problem (preliminary version). Proc. 13th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2019), LNCS11949, pp.1-12, the City Hotel Xiamen, Xiamen, China (December 13 – December 15, 2019). DOI:10.1007/978-3-030-36412-0_1
Yuichi Asahiro, Tomohiro Kubo, Eiji 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 (October, 2019). DOI:10.1007/s12626-019-00036-2
Yuichi Asahiro, Guohui Lin, Zhilong Liu, and Eiji Miyano. An approximation algorithm for the maximum induced matching problem on C5-free regular graphs. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E102-A, No.9, pp.1142-1149 (September 1, 2019). DOI:10.1587/transfun.E102.A.1142
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Sandhya T.P.. Graph Orientation with Edge Modifications (preliminary version). Proc. 13th International Frontiers of Algorithmics Workshop (FAW 2019), LNCS11458, pp.38-50, Tsinghua Sanya International Mathematics Forum (TSIMF), Sanya, China (April 29 – May 3, 2019). DOI:10.1007/978-3-030-18126-0_4
2018
Weitian Tong, Eiji Miyano, Randy Goebel, Guohui Lin. An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops. Theoretical Computer Science, Vol.734, pp.24-31 (July 22, 2018). DOI: 10.1016/j.tcs.2017.09.018
Yuichi Asahiro, Eiji Miyano, Tsuyoshi Yagita. Approximation Algorithms for Packing Directed Acyclic Graphs into Two-Size Blocks (preliminary version). Proc. 18th International Conference on Computational Science and Its Applications (ICCSA 2018), LNCS10961, pp.607-623, Monash University, Caulfield Campus, Melbourne, Australia (July 1-4, 2018). DOI:10.1007/978-3-319-95165-2_43
Yuichi Asahiro, Yuya Doi, Eiji Miyano, Kazuaki Samizo, Hirotaka Shimizu. Optimal approximation algorithms for maximum distance-bounded subgraph problems. Algorithmica, Vol.80, No.6, pp.1834-1856 (June, 2018). DOI:10.1007/s00453-017-0344-y
Peng Zhang, Yao Xu, Tao Jian, Angsheng Li, Guohui Lin, Eiji Miyano. Improved approximation algorithms for the maximum happy vertices and edges problems. Algorithmica, Vol.80, No.5, pp.1412-1438 (May, 2018). DOI:10.1007/s00453-017-0302-8
Yuichi Asahiro, Jeper Jansson, Eiji Miyano, Hesam Nikpey, Hirotaka Ono. Graph orientation with splits (preliminary version). Proc. 5th International Symposium on Combinatorial Optimization (ISCO2018), LNCS10856, pp.52-63, Palm Plaza Hotel & Spa 5, Marrakesh, Morocco (April 11-13, 2018). DOI:10.1007/978-3-319-96151-4_5
Eiji Miyano, Toshiki Saitoh, Ryuhei Uehara, Tsuyoshi Yagita, and Tom C. van der Zanden. Complexity of the maximum k-path vertex cover problem (preliminary version). Proc. 12th Annual Workshop on Algorithms and Computation (WALCOM 2018), LNCS10755, pp.240-251, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), ECE building, West Palasi, Dhaka, Bangladesh (March 3-5, 2018). DOI:10.1007/978-3-319-75172-6
Hiroshi Eto, Hiroyuki Kawahara, Eiji Miyano, and Natsuki Nonoue. Complexity of the minimum single dominating cycle problem for graph classes. IEICE TRANSACTIONS on Information and Systems, Vol.E101-D, No.3, pp.574-581 (March 1, 2018). DOI: 10.1587/transinf.2017FCP0007
2017
Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano. Approximation algorithm for the distance-3 independent set problem on cubic graphs. Proc. 11th International Conference and Workshops on Algorithms and Computation (WALCOM2017), LNCS10167, pp.228-240, Microelectronics and Information System Research Center, National Chiao Tung University, Hsinchu, Taiwan (March 29 – 31, 2017). DOI:10.1007/978-3-319-53925-6_18
2016
Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano. Approximability of the distance independent set problem on regular graphs and planar graphs (preliminary version). Proc. 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA2016), LNCS10043, pp.270-284, City University of Hong Kong, Hong Kong, China (December 16 – 18, 2016). DOI:10.1007/978-3-319-48749-6_20
Yuichi Asahiro, Tomohiro Kubo, Eiji Miyano. Experimental evaluation of approximation algorithms for maximum distance-bounded subgraph problems. Proc. Joint 8th International Conference on Soft Computing and Intelligent Systems and 17th International Symposium on Advanced Intelligent Systems, pp.892-897, Hokkai-Gakuen University, Sapporo, Hokkaido, Japan (August 25-28, 2016).
DOI: 10.1109/SCIS-ISIS.2016.0193Weitian Tong, Eiji Miyano, Randy Goebel, Guohui Lin. A PTAS for the multiple parallel identical multi-stage flow-shops to minimize the makespan (preliminary version). Proc. 10th International Frontiers of Algorithmics Workshop (FAW 2016), LNCS9711, pp.227-237, Qingdao University, Qingdao, China (June 30 – July 2, 2016). DOI:10.1007/978-3-319-39817-4_22
Daiki Hoshika, Eiji Miyano. Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science, Vol.E99-A, No.6, pp.1059-1066 (June 1, 2016).
DOI: 10.1587/transfun.E99.A.1059Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation. Theory of Computing Systems, Vol.58, No.1, pp.60-93 (January 2016). DOI:10.1007/s00224-014-9565-5
2015
Yuichi Asahiro, Yuya Doi, Eiji Miyano, Hirotaka Shimizu. Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems. Proc. 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015), LNCS 9486, pp.586-600, Houston Marriott West Loop by the Galleria, Houston, USA (December 18-20, 2015). DOI:10.1007/978-3-319-26626-8_43
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Graph Orientations Optimizing the Number of Light or Heavy Vertices. Journal of Graph Algorithms and Applications, Vol.19, No.1, pp.441-465 (August 1, 2015). DOI:10.7155/jgaa.00371
2014
Eiji Miyano and Keisuke Tahara. Evolutionary Algorithms for the Pursuit Problem. Proc. Joint 7th International Conference on Soft Computing and Intelligent Systems and 15th International Symposium on Advanced Intelligent Systems, 6 pages, Kitakyushu International Conference Center, Fukuoka, Japan (December 3-6, 2014). DOI:10.1109/SCIS-ISIS.2014.7044840
Yuichi Asahiro, Hiroshi Eto, Eiji Miyano, Takehiro Ito. Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree. Theoretical Computer Science, Vol.550, 18, 21-35 (September 18, 2014). DOI:10.1016/j.tcs.2014.07.008
Daiki Hoshika, Eiji Miyano. Approximation Algorithms for Packing Element-Disjoint Steiner Trees on Bounded Terminal Nodes (Preliminary version). Proc. 10th International Conference on Algorithmic Aspects of Information and Management (AAIM 2014), LNCS8546, pp.100–111, Harbour Centre, Simon Fraser University, Vancouver, BC, Canada (July 8-11, 2014). DOI:10.1007/978-3-319-07956-1_10
Hiroshi Eto, Fengrui Guo, Eiji Miyano. Distance-d Independent Set Problems for Bipartite and Chordal Graphs. Journal of Combinatorial Optimization, Vol.27, Issue 1, pp.88-99 (January 2014). DOI:10.1007/s10878-012-9594-4
2013
Yuichi Asahiro, Kenta Kanmera, Eiji Miyano. (1+ε)-competitive algorithm for online OVSF code assignment with resource augmentation. Journal of Combinatorial Optimization, Vol.26, Issue 4, pp.687-708 (November 2013). DOI:10.1007/s10878-012-9454-2
Yuichi Asahiro, Eiji Miyano, Toshihide Murata, Hirotaka Ono. Optimal approximability of bookmark assignments. Discrete Applied Mathematics, Vol.161, Issues 16-17, pp.2361-2366 (November 2013). DOI:10.1016/j.dam.2013.05.018
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation (preliminary Version). Proc. 11th International Workshop on Approximation and Online Algorithms (WAOA2013), LNCS 8447, pp.24–36, Sophia Antipolis, France (September 2013). DOI:10.1007/978-3-319-08001-7_3
Yuichi Asahiro, Hiroshi Eto, Eiji Miyano, Takehiro Ito. Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree (preliminary Version). Proc. 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), LNCS 8070, pp.28-39, Crowne Plaza Liverpool, Liverpool, United Kingdom (August 19-21, 2013). DOI:10.1007/978-3-642-40164-0_6
Yuichi Asahiro, Hiroshi Eto, Eiji Miyano. Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems. IEICE Transactions on Information and Systems (Special Section on Foundations of Computer Science – New Trends in Algorithms and Theory of Computation -), Vol.E96-D, No.3, pp.443-449 (March 1, 2013). DOI:10.1587/transinf.E96.D.443
2012
Hiroshi Eto, Fengrui Guo, Eiji Miyano. Distance-d Independent Set Problems for Bipartite and Chordal Graphs (Preliminary Version). Proc. 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), LNCS 7402, pp.234-244, Banff Centre, Banff, Canada (August 5-9, 2012). DOI:10.1007/978-3-642-31770-5_21
Yuichi Asahiro, Kenichi Kawahara, Eiji Miyano. NP-hardness of the sorting buffer problem on the uniform metric. Discrete Applied Mathematics, Vol.160, Issues 10-11, pp.1453-1464 (July 2012). DOI:10.1016/j.dam.2012.02.005
Masao Kumamoto, Eiji Miyano. Optimal distortion embedding of complete binary trees into lines. Information Processing Letters, Vol.112, No.10, pp.365-370 (May 31, 2012). DOI:10.1016/j.ipl.2012.02.003
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Graph Orientations Optimizing the Number of Light or Heavy Vertices (Preliminary Version). Proc. 2nd International Symposium on Combinatorial Optimization (ISCO 2012), LNCS 7422, pp.332-343, the Athens University of Economics and Business, Athens, Greece (April 19-21, 2012). DOI:10.1007/978-3-642-32147-4_30
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Upper and Lower Degree Bounded Graph Orientation with Minimum Penalty. Proc. Computing: The 18th Australasian Theory Symposium (CATS 2012), CRPIT, Vol.128, pp.139-146, Storey Hall, RMIT University, Melbourne, Australia (January 30 – February 2, 2012).
2011
Yuichi Asahiro, Kenta Kanmera, Eiji Miyano. (1+ε)-Competitive Algorithm for Online OVSF Code Assignment with Resource Augmentation (Preliminary Version). Proc. 17th Annual International Computing and Combinatorics Conference (COCOON 2011), LNCS 6842, pp.259-270, DoubleTree by Hilton Hotel Dallas, Richardson, Texas, USA (August 14-16, 2011). DOI:10.1007/978-3-642-22685-4_24
Yuichi Asahiro, Hiroshi Eto, Eiji Miyano. Inapproximability of Maximum r-Regular Induced Connected Subgraph Problems (Preliminary Version). Proc. the 2011 International Conference of Foundation of Computer Science (FCS’2011), pp.102-107, Las Vegas, Nevada, USA (July 18-21, 2011)
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Kouhei Zenmyo. Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree. Journal of Combinatorial Optimization, Vol.22, No.1, pp.78-96 (July 2011). DOI:10.1007/s10878-009-9276-z
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Graph orientation to maximize the minimum weighted outdegree. International Journal of Foundations Computer Science, Vol.22, No.3, pp.583-601 (April 2011). DOI: 10.1142/S0129054111008246
Yuichi Asahiro, Eiji Miyano, Hirotaka Ono. Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree. Discrete Applied Mathematics, Vol.159, No.7 (April 2011). DOI:10.1016/j.dam.2010.11.003
Eiji Miyano and Hirotaka Ono. Maximum Domination Problem. Proc. Computing: The 17th Australasian Theory Symposium (CATS 2011), CRPIT, Vol.119, Alex Potanin and Taso Viglas Eds., ACS. pp.55-61, Curtin University, Perth, Australia (January 2011)
2010
Masao Kumamoto, Eiji Miyano. Optimal Distortion Embedding of Complete Binary Trees into Lines (Preliminary Version). Proc. the 2010 International Conference of Foundation of Computer Science (FCS’2010), pp.16-21, Las Vegas, Nevada, USA (July 12-15, 2010)
Yuichi Asahiro, Eiji Miyano, Kazuaki Samizo. Approximating Maximum Diameter-Bounded Subgraphs. Proc. The 9th Latin American Theoretical Informatics Symposium (LATIN2010), LNCS 6034, pp.615-626, University of Oaxaca and Hotel Victoria, Oaxaca, Mexico (April 2010). DOI:10.1007/978-3-642-12200-2_53
Yuichi Asahiro, Eiji Miyano, Shuichi Miyazaki, Takuro Yoshimuta. Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles. Information Processing Letters, Vol.110, No.3, pp.93-98 (January 2010). DOI:10.1016/j.ipl.2009.10.013
2009
Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono. Graph Orientation to Maximize the Minimum Weighted Outdegree (Preliminary Version). Proc. 11th Workshop on Advances in Parallel and Distributed Computation Models, IPDPS 2009, APDCM 2009, pp.1-8 (May 2009). DOI: 10.1109/IPDPS.2009.5160872
Kazuo Iwama, Eiji Miyano, Hirotaka Ono. Drawing borders efficiently. Theory of Computing Systems, Vol.44, No.2, pp.230-244 (February 2009). DOI:10.1007/s00224-008-9117-y
Naoyuki Kamiyama, Yuuki Kiyonari, Eiji Miyano, Shuichi Miyazaki, Katsuhisa Yamanaka. Computational complexities of university interview timetabling. IEICE Transactions on Information and Systems, Vol.E92-D, No.2, pp.130-140 (February 2009). DOI:10.1587/transinf.E92.D.130
2008
Yuichi Asahiro, Kenichi Kawahara, Eiji Miyano. NP-Hardness of the Sorting Buffer Problem on the Uniform Metric (Preliminary Version). Proc. the 2008 International Conference of Foundation of Computer Science (FCS’08), pp.137-143, Las Vegas, Nevada, USA (July 14-17, 2008)
Yuichi Asahiro, Eiji Miyano, Shinichi Shimoirisa. Grasp and delivery for moving objects on broken lines. Theory of Computing Systems, Vol.42, No.3, pp.289-305 (April 2008). DOI:10.1007/s00224-007-9081-y
Yuichi Asahiro, Eiji Miyano, Hirotaka Ono. Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree (Preliminary Version). Proc. Computing: The 14th Australasian Theory Symposium (CATS 2008), CRPIT, Vol.77, Harland, J. and Manyem, P. Eds, ACS. pp.97-106, Wollongong, NSW, Australia (January 2008). DOI:
2007
(Preliminary Version) Yuichi Asahiro, Eiji Miyano, Toshihide Murata, Hirotaka Ono. On Approximation of Bookmark Assignments. Proc. 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2007), LNCS 4708, pp.115-124, Hotel Ruze, Cesky Krumolov (UNESCO World Heritage Site), Czech Republic (August 26-31, 2007). DOI:10.1007/978-3-540-74456-6_12
(Preliminary Version) Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Kouhei Zenmyo. Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree. Proc. 3rd International Conference on Algorithmic Aspects in Information and Management (AAIM 2007), LNCS 4508, pp.167-177, Washington State University Vancouver Campus, WA (or Portland, OR), USA (June 6-8, 2007). DOI:10.1007/978-3-540-72870-2_16
(Preliminary Version) Kazuo Iwama, Eiji Miyano, Hirotaka Ono. Drawing Borders Efficiently. Proc. 4th International Conference on FUN WITH ALGORITHMS (FUN 2007), LNCS 4475, pp.213-226, Castiglioncello (LI), Tuscany, Italy (June 2007). DOI:10.1007/978-3-540-72914-3_19
Yuichi Asahiro, Eiji Miyano, Hirotaka Ono, Kouhei Zenmyo. Graph Orientation Algorithms to Minimize the Maximum Outdegree. International Journal of Foundation of Computer Science, Vol.18, No.2, pp.197-216 (April 2007). DOI:10.1142/S0129054107004644
(Preliminary Version) Yuichi Asahiro, Eiji Miyano, Shuichi Miyazaki, Takuro Yoshimuta. Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles. Proc. 33rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2007), LNCS 4362, pp.164-175, Hotel Sklar, Harrachov, Czech Republic (January 2007). DOI:10.1007/978-3-540-69507-3_13
2006
Yuuki Kiyonari, Eiji Miyano, Shuichi Miyazaki. Computational Complexity Issues in University Interview Timetabling. Proc. 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006), pp.448-453, Hotel International Brno, Brno, The Czech Republic (August 30 – September 1, 2006)
Takahiro Yukizane, Shin-ya Ohi, Eiji Miyano, Hideo Hirose. The Bump Hunting Method Using the Genetic Algorithm with the Extreme-Value Statistics. Special Issue on Invited Papers from New Horizons in Computing, IEICE Transactions on Information and Systems, Vol.E89-D, No.8, pp.2332-2339 (August, 2006).
Hideo Hirose, Takahiro Yukizane, Eiji Miyano. Boundary detection for bumps using the Gini’s index in messy classification problems. Proc. 3rd International Conference on Cybernetics and Information Technologies, Systems and Applications, pp.293-297, Sheraton World Resort, Orlando, Florida, USA (July 2006)
Yuichi Asahiro, Tetsuya Furukawa, Keiichi Ikegami, Eiji Miyano. How to pack directed acyclic graphs into small blocks (preliminary version). Proc. 6th Conference on Algorithms and Complexity (CIAC 2006), LNCS 3998, pp.272-283, University of Rome, Rome, Italy (May 29-31, 2006). DOI:10.1007/11758471_27
Yuichi Asahiro, Eiji Miyano, Hirotaka Ono, Kouhei Zenmyo. Graph Orientation Algorithms to Minimize the Maximum Outdegree (preliminary version). Proc. Computing: The Twelfth Australasian Theory Symposium (CATS 2006), pp.11-20, Wrest Point Casino Hotel, Tasmania, Australia (January 2006). DOI:
Hideo Hirose, Takahiro Yukizane, Eiji Miyano. The bump hunting method using the genetic algorithm and the extreme-value statistics with application to a messy customer database. 2006 Hawaii International Conference on Statistics, Mathematics and Related Fields, Hawaii, USA (January 2006)
2005
Yuichi Asahiro, Eiji Miyano, Shinichi Shimoirisa. Pickup and delivery for moving objects on broken lines (preliminary version). Proc. 9th Italian Conference on Theoretical Computer Science (ICTCS 2005), LNCS 3701, pp.36-50, Certosa di Pontignano, Siena, Italy (October 2005). DOI:10.1007/11560586_5
Yuichi Asahiro, Eiji Miyano, Shinichi Shimoirisa. K-Collect Tours for Moving Objects with Release Times and Deadlines. Proc. 9th World Multi-Conference on Systemics, Cybernetics, and Informatics, Vol.III, pp.192-197, Rozen Centre Hotel, Orland, Florida, USA (July 10-15, 2005)
2004
2003
2002
2001
Kazuo Iwama, Eiji Miyano. An O(\sqrt{N}) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size. Journal of Algorithms, Vol.41, Issue 2, pp.262-279 (November 2001). DOI:10.1006/jagm.2001.1176
Kazuo Iwama, Eiji Miyano. A Lower Bound for Elementary Oblivious Routing on Three-Dimensional Meshes. Journal of Algorithms, Vol.39, Issue 2, pp.145-161 (May 2001). DOI:10.1006/jagm.2000.1152
Kazuo Iwama, Yahiko Kambayashi, Eiji Miyano. New Bounds for Oblivious Mesh Routing. Journal of Graph Algorithms and Applications, Vol.5, No.5, pp.17-38 (2001) (Graph Algorithms and Applications 2, pp.433-454 (2004), World Scientific Pub Co Inc, ISBN-10:9812388559, DOI:10.1142/5550 )
Kazuo Iwama, Eiji Miyano, Satoshi Tajima, Hisao Tamaki. Efficient randomized routing algorithms on the two-dimensional mesh of buses. Theoretical Computer Science, Vol.261, Issue 2, pp.227-239 (June 28, 2001) DOI:10.1016/S0304-3975(00)00141-9
2000
Kazuo Iwama, Eiji Miyano. A (2.954+e)n oblivious routing algorithm on 2D Meshes. Proc. 12th ACM Symposium on Parallel Algorithms and Architectures (SPAA2000), pp.186-195, Bar Harbor, Maine, USA (July 9-13, 2000). DOI:10.1145/341800.341822
Kazuo Iwama, Eiji Miyano. Recent Developments in Mesh Routing Algorithms (Invited Survey Paper). Special Issue on Algorithms Engineering: Surveys, IEICE Transactions on Information and Systems, Vol.E83-D, No.3, pp.530-540 (March 25, 2000)
Kazuo Iwama, Eiji Miyano. Oblivious Routing Algorithms on the Mesh of Buses. Journal of Parallel and Distributed Computing, Vol.60, No.2, pp.137-149 (February, 2000). DOI:10.1006/jpdc.1999.1597
1999
Kazuo Iwama, Eiji Miyano. Multipacket Routing on 2-D meshes and Its Applications to Fault-Tolerant Routing. Proc. Seventh Annual European Symposium on Algorithms (ESA’99), LNCS 1643, pp.53-64, Prague, Czech Republic (July 16-18, 1999). DOI:10.1007/3-540-48481-7_6
(Preliminary Version) Kazuo Iwama, Eiji Miyano. An O(\sqrt{N}) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size. Proc. Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’99), pp.466-475, Omni Inner Harbor Hotel, Baltimore, Maryland (January 17-19, 1999).
1998
Kazuo Iwama, Yahiko Kambayashi, Eiji Miyano. New Bounds for Oblivious Mesh Routing (preliminary version). Proc. Sixth Annual European Symposium on Algorithms (ESA’98), LNCS 1461, pp.295-306, Venice, Italy (August 24-26, 1998) DOI:10.1007/3-540-68530-8_25
Kazuo Iwama, Eiji Miyano, Satoshi Tajima, Hisao Tamaki. Efficient randomized routing algorithms on the two-dimensional mesh of buses (preliminary version). Proc. Fourth Annual International Computing and Combinatorics Conference (COCOON98), LNCS 1449, pp.229-240, Academia Sinica, Taipei, Taiwan, ROC, (August 12-14, 1998) DOI:10.1007/3-540-68535-9_27
Kazuo Iwama, Eiji Miyano. Better approximations of non-Hamiltonian graphs. Discrete Applied Mathematics, Vol.81, Issues 1-3, pp.239–261 (January 15, 1998). DOI:10.1016/S0166-218X(97)00099-1
1997
Kazuo Iwama, Eiji Miyano. Three-Dimensional Meshes Are Less Powerful than Two-Dimensional Ones in Oblivious Routing (preliminary version). Proc. 5th European Symposium on Algorithms (ESA’97), LNCS 1284, pp.284-295, Graz, Austria (September 15-17, 1997). DOI:10.1007/3-540-63397-9_22
Kazuo Iwama, Eiji Miyano. Oblivious Routing Algorithms on the Mesh of Buses (preliminary version). Proc. 11th International Parallel Processing Symposium (IPPS’97), pp.721-727, The University of Geneva, Geneva, Switzerland (April 1-5, 1997). DOI:10.1109/IPPS.1997.580986
1996
Yuichi Asahiro, Kazuo Iwama, Eiji Miyano. Random Generation of Test Instances with Controlled Attributes (Book Chapter). In Cliques, Coloring, and Satisfiability, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol.26, D.S. Johnson and M.A. Trick, Ed., 377-393, American Mathematical Society (1996). ISBNs: 978-0-8218-6609-2 (print); 978-1-4704-3984-2 (online). DOI:10.1090/dimacs/026
Kazuo Iwama, Eiji Miyano, Yahiko Kambayashi. Routing Problems on the Mesh of Buses. Journal of Algorithms, Vol.20, Issue 3, pp.613-631 (May 1996). DOI:10.1006/jagm.1996.0030
1995
Kazuo Iwama, Eiji Miyano. Intractability of Read-Once Resolution. Proc. Tenth IEEE Conference on Structure in Complexity Theory, pp.29-36, Minneapolis, MN, USA (June 19-22, 1995). DOI:10.1109/SCT.1995.514725
1994
1993
Kazuo Iwama and Eiji Miyano. Test-Case Generation with Known Answers and Proved Securities (preliminary Version) . Proc. Second DIMACS Challenge Workshop (Satisfiability), New Jersey, USA (October 1993)
Kazuo Iwama, Eiji Miyano. Security of Test-Case Generation with Known Answers. Proc. AAAI Spring Symposium Series, pp.85-91, Stanford, USA (March 1993)
1992
Kazuo Iwama, Eiji Miyano, Yahiko Kambayashi. Routing Problems on the Mesh of Buses (preliminary Version). Proc. Third International Symposium on Algorithms and Computation (ISAAC’92), LNCS 650, pp.155-164, Nagoya (December 1992). DOI:10.1007/3-540-56279-6_68
Kazuo Iwama, Hidetoshi Abeta, Eiji Miyano. Random Generation of Satisfiable and Unsatisfiable CNF Predicates. Proc. the IFIP 12th World Computer Congress, Vol.1, pp.322-328, Madrid, Spain (September 1992)
1991
Kazuo Iwama, Eiji Miyano, Yahiko Kambayashi. Time Bounds for Sorting and Routing Problems on Mesh-Bus Computers. Proc. Joint Symposium on Parallel Processing ’91 (JSPP’91), pp.453-460, Koube, Japan (May, 1991)
Talks in International Workshops/Meetings
Yuichi Asahiro, Jesper Jansson, Avraham Melkman, Eiji Miyano, Hirotaka Ono, Quan Xue and Shay Zakov. Shortest Longest-Maximal-Path Orientation for Trees (one-page abstract). The 15th Asian Association for Algorithms and Computation Annual Meeting (AAAC 2024). May 31 - June 1, 2024, I-site Namba (Facility of Osaka Metropolitan University), Osaka, Japan (May 2024)
Yuichi Asahiro, Hiroshi Eto, Taku Kato, Guohui Lin and Eiji Miyano. Bounded-Deletion Maximum Independent Set Problem on Chordal Bipartite Graphs (one-page abstract). The 15th Asian Association for Algorithms and Computation Annual Meeting (AAAC 2024). May 31 - June 1, 2024, I-site Namba (Facility of Osaka Metropolitan University), Osaka, Japan (May 2024)
Eiji Miyano. Bounded-deletion max independent set and bounded-deletion max clique for graph classes. International Workshop on Discrete Mathematics and Algorithms 2024 (no proceedings), March 27-29, 2024, Room A130 (Glen Grant Theater), Hawaii Tokai International College, Kapolei, Hawaii, USA (March 2024)
Yuichi Asahiro, Guohui Lin, Zhilong Liu, Eiji Miyano. On the Approximability of the Maximum Induced Matching Problem on Regular Graphs (one-page abstract). Proceedings of 12th Asian Association for Algorithms and Computation Annual Meeting (AAAC19), April 19-21, Department of Computer Science of Yonsei University, Seoul, South Korea (April 2019)
Eiji Miyano. Efficient algorithm design for combinatorial optimization problems. Robotics and Computer Science, September 8, Steinman Hall of the Grove School of Engineering, the City College of New York, New York (September 2017)
Yuichi Asahiro, Eiji Miyano, Tsuyoshi Yagita. Approximation algorithms for the minimum block transfer problem (one-page abstract). The 10th Asian Association for Algorithms and Computation Annual Meeting (AAAC17), May 5-7, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong (May 2017)
Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano. An improved approximation algorithm for the distance-3 independent set problem on cubic graphs (one-page abstract). The 10th Asian Association for Algorithms and Computation Annual Meeting (AAAC17), May 5-7, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong (May 2017)
Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano. Regular induced subgraphs in bipartite and planar graphs. Proc. 19th Japan-Korean Joint Workshop on Algorithms and Computation (WAAC 2016), 43-1-8, August 30-31, Hakodate Citizen Hall, Hakodate, Hokkaido, Japan (August 2016)
Ei Ando, Akitoshi Kawamura, Masashi Kiyomi, Eiji Miyano, Hirotaka Ono. Logging with maximum length constraint. Proc. 19th Japan-Korean Joint Workshop on Algorithms and Computation (WAAC 2016), 4 pages, August 30-31, Hakodate Citizen Hall, Hakodate, Hokkaido, Japan (August 2016)
Yuichi Asahiro, Yuya Doi, Eiji Miyano, Hirotaka Shimizu. Approximation algorithms to find maximum distance-bounded subgraphs (one-page abstract). The 9th Asian Association for Algorithms and Computation Annual Meeting (AAAC16), p.11, May 14-16, Taipei, Taiwan (May 2016)
Hiroshi Eto, Zhilong Liu, Eiji Miyano. Simple approximation algorithms for the distance-3 independent set problem on cubic graphs (one-page abstract). The 9th Asian Association for Algorithms and Computation Annual Meeting (AAAC16), p.xx, May 14-16, Taipei, Taiwan (May 2016)
Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano. Maximum r-Regular Induced Subgraph Problems for Chordal Bipartite Graphs (one-page abstract). Seventh Asian Association for Algorithms and Computation Annual Meeting (AAAC14), Page 18, May 17-19, Hangzhou, China (May 2014)
Yuichi Asahiro, Yuya Doi, Eiji Miyano, Hirotaka Shimizu. Maximum Diameter-Bounded Subgraphs in Intersection Graphs. Proc. The 16th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC 2013), pp.83–90, July 12-13, Kyonggi University, Suwon, Korea (July 2013)
Yuichi Asahiro, Yuya Doi, Eiji Miyano, Hirotaka Shimizu. Maximum Diameter-Bounded Subgraphs in Graphs Without Long Induced Cycles (one-page abstract). Sixth Asian Association for Algorithms and Computation Annual Meeting (AAAC13), Page 24, April 19-21, Matsushima, Japan (April 2013)
Yuichi Asahiro, Hiroshi Eto, Eiji Miyano. Improved Inapproximability of Regular Induced Connected Subgraph Problems. Proc. The 15th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2012), pp.161-168, July 10-11, National Institute of Informatics, Tokyo, Japan (July 2012)
Yuichi Asahiro, Hiroshi Eto, Eiji Miyano. W[1]-Hardness of Regular Induced Connected Subgraph Problems (one-page abstract). Fifth Asian Association for Algorithms and Computation Annual Meeting (AAAC12), Page 19, April 21-22, Fundan University, Shanghai, China (April 2012)
Hiroshi Eto, Fengrui Guo, Eiji Miyano. Distance-d Independent Set Problems (one-page abstract). Fifth Asian Association for Algorithms and Computation Annual Meeting (AAAC12), Page 20, April 21-22, Fundan University, Shanghai, China (April 2012)
Eiji Miyano and Hirotaka Ono. Maximum Edge Domination Problem (one-page abstract). Fourth Asian Association for Algorithms and Computation Annual Meeting (AAAC11), Page 66, April 16-17, Hsinchu, Taiwan (April 2011)
Yuichi Asahiro, Kenta Kanmera, Eiji Miyano. 2-Competitive Algorithm for Online OVSF Code Assignment with Small Resource Augmentation (one-page abstract). Fourth Asian Association for Algorithms and Computation Annual Meeting (AAAC11), Page 69, April 16-17, Hsinchu, Taiwan (April 2011)
Yuichi Asahiro, Kenichi Kawahara, Eiji Miyano. NP-Hardees of the Sorting Buffer Problem on the Uniform Metric (one-page abstract). First Asian Association for Algorithms and Computation Annual Meeting (AAAC08), Page 25, April 26-27, Hong Kong (April 2008)
Kazuo Iwama and Eiji Miyano. New Techniques in 2-D Mesh Routing. ACM/UMIACS Workshop on Parallel Algorithms (WoPA’99), May 4-5, 1999, Atlanta, Georgia, USA (May 1999)
Kazuo Iwama and Eiji Miyano. New Bounds for Oblivious Mesh Routing. SPAA98 Revue, Puerto Vallarta, Mexico (June 1998)