List of Papers
Journal Publications

Jianshen Zhu, Naveed Ahmed Azam, Kazuya Haraguchi, Liang Zhao, Hiroshi Nagamochi, Tatsuya Akutsu : An Inverse QSAR Method Based on Linear Regression and Integer Programming Frontiers in Bioscience-Landmark (to appear) F. Zhang, J. Zhu, R. Chiewvanichakorn, A. Shurbevski, H. Nagamochi, T. Akutsu : A New Approach to the Design of Acyclic Chemical Compounds Using Skeleton Trees and Integer Linear Programming Applied Intelligence (APIN) (2022) DOI 10.1007/s10489-021-03088-6. Kazuya Haraguchi, Hiroshi Nagamochi : Enumeration of Support-Closed Subsets in Confluent Systems Algorithmica (2022) DOI:10.1007/s00453-022-00927-x i m, [, AZAM Naveed Ahmed, a, , v B : @BwKQSAR̐v@ɊÂt͖@ Journal of Computer Chemistry, 2021 N 20 3 p. 106-111 Seok-Hee Hong, Hiroshi Nagamochi : Re-embedding a 1-Plane Graph for a Straight-line Drawing in Linear Time Theoretical Computer Science, 892: 132-154 (2021). Naveed Ahmed Azam, Aleksandar Shurbevski, Hiroshi Nagamochi : On the Enumeration of Minimal Non-Pairwise Compatibility Graphs Journal of Combinatorial Optimization (to appear). J. Zhu, N. A. Azam, F. Zhang, A. Shurbevski, K. Haraguchi, L. Zhao, H. Nagamochi, T. Akutsu : A novel method for inferring chemical compounds with prescribed topological substructures based on integer programming Transaction on Computational Biology and Bioinformatics, doi: 10.1109/TCBB.2021.3112598 N. A. Azam, J. Zhu, Y. Sun, Y. Shi, A. Shurbevski, L. Zhao, H. Nagamochi, T. Akutsu : A novel method for inference of acyclic chemical compounds with bounded branch-height based on artificial neural networks and integer programming Algorithms for Molecular Biology, 16, 18 (2021). Naveed Ahmed Azam, Aleksandar Shurbevski, Hiroshi Nagamochi : A method for enumerating pairwise compatibility graphs with a given number of vertices Discrete Applied Mathematics, Volume 303, 15 November 2021, Pages 171-185. Yu Shi, Jianshen Zhu, Naveed Ahmed Azam, Kazuya Haraguchi, Liang Zhao, Hiroshi Nagamochi, Tatsuya Akutsu : An inverse QSAR method based on a two-layered model and integer programming International Journal of Molecular Sciences, 2021, 22, 2847. Yuhei Fukui, Aleksandar Shurbevski, Hiroshi Nagamochi : Group Strategy-proof Mechanisms for Shuttle Facility Games J. Inf. Process., 28: 976-986 (2020). Naveed Ahmed Azam, Aleksandar Shurbevski, Hiroshi Nagamochi : Enumerating Tree-Like Graphs and Polymer Topologies with a Given Cycle Rank Entropy, 2020, 22(11), 1295. Mingyu Xiao, Hiroshi Nagamochi : Characterizing Star-PCGs Algorithmica 82(10): 3066-3090 (2020). Naveed Ahmed Azam, Aleksandar Shurbevski, Hiroshi Nagamochi : An Efficient Algorithm to Count Tree-Like Graphs with a Given Number of Vertices and Self-Loops Entropy, 2020, 22(9), 923. Jianshen Zhu, Chenxi Wang, Aleksandar Shurbevski, Hiroshi Nagamochi, Tatsuya Akutsu : A Novel Method for Inference of Chemical Compounds of Cycle Index Two with Desired Properties Based on Artificial Neural Networks and Integer Programming Algorithms 2020, 13(5), 124; 18 May 2020 Xiao, M., Nagamochi, H. : Some reduction operations to pairwise compatibility graphs Information Processing Letters, 153, 105875 (2020). Yuhei Fuki, Aleksandar Shurbevski, Hiroshi Nagamochi : -Group Strategy-Proof Mechanisms for the Obnoxious Facility Game in Star Networks Journal IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E102-A, No.9, pp.1179-1186, 2019. Akane Seto, Aleksandar Shurbevski, Hiroshi Nagamochi, Peter Eades : Acute Constraints in Straight-Line Drawings of Planar Graphs Journal IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E102-A, No.9, pp.994-1001, 2019. Seok-Hee Hong, Hiroshi Nagamochi : A linear-time algorithm for testing full outer-2-planarity Discrete Applied Mathematics 255: 234-257 (2019) K. Haraguchi, Y. Momoi, A. Shurbevski, H. Nagamochi : COOMA: a components overlaid mining algorithm for enumerating connected subgraphs with common itemsets Journal of Graph Algorithms and Applications, 23(2):434-458, 2019 Yuhei Nishiyama, Aleksandar Shurbevski, Hiroshi Nagamochi, Tatsuya Akutsu : Resource Cut, a New Bounding Procedure to Algorithms for Enumerating Tree-Like Chemical Graphs IEEE/ACM Trans. Comput. Biology Bioinform. 16(1): 77-90 (2019) Seok-Hee Hong, Hiroshi Nagamochi : Simpler algorithms for testing two-page book embedding of partitioned graphs Theor. Comput. Sci. 725: 79-98 (2018) Mohd Shahrizan Othman, Aleksandar Shurbevski, Hiroshi Nagamochi : Polynomial-Space Exact Algorithms for the Bipartite Traveling Salesman Problem IEICE Transactions 101-D(3): 611-612 (2018) Hiroaki Suto, Aleksandar Shurbevski, Hiroshi Nagamochi : The Stable Roommates Problem with Unranked Entries IEICE Transactions 101-A(9): 1412-1419 (2018) Jinghui Li, Hiroshi Nagamochi, Tatsuya Akutsu : Enumerating Substituted Benzene Isomers of Tree-Like Chemical Graphs IEEE/ACM Trans. Comput. Biology Bioinform. 15(2): 633-646 (2018) Mingyu Xiao, Hiroshi Nagamochi : Exact algorithms for maximum independent set Inf. Comput. 255: 126-146 (2017) Morito Oomine, Aleksandar Shurbevski, Hiroshi Nagamochi : Parameterization of Strategy-Proof Mechanisms in the Obnoxious Facility Game J. Graph Algorithms Appl. 21(3): 247-263 (2017) Mingyu Xiao, Hiorshi Nagamochi : A refined algorithm for maximum independent set in degree-4 graphs J. Comb. Optim. 34(3): 830-873 (2017) Mingyu Xiao, Hiroshi Nagamochi : Complexity and kernels for bipartition into degree-bounded induced graphs Theor. Comput. Sci. 659: 72-82 (2017) K. Iwaide, H. Nagamochi : An Exact Algorithm for Lowest Edge Dominating Set IEICE Transactions Inf. and Syst. Vol. E100. D (2017) No. 3 pp. 414-421. M. Oomine, H. Nagamochi : Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees IEICE Transactions Inf. and Syst., vol. E99-D, no. 3, 615 - 623 March 2016. Ken Iwaide, Hiroshi Nagamochi : An Improved Algorithm for Parameterized Edge Dominating Set Problem J. Graph Algorithms Appl. 20(1): 23-58 (2016) Mingyu Xiao, Hiroshi Nagamochi : An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure Algorithmica 74(2): 713-741 (2016) Mingyu Xiao, Hiroshi Nagamochi : An exact algorithm for maximum independent set in degree-5 graphs Discrete Applied Mathematics 199: 137-155 (2016) M. Xiao, H. Nagamochi : An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4 Theory of Computing Systems, 58(2): 241-272 (2016) M. Xiao, H. Nagamochi : Exact algorithms for dominating induced matching based on graph partition Discrete Applied Mathematics 190: 147-162 (2015) M. Xiao, H. Nagamochi : An improved exact algorithm for undirected feedback vertex set J. of Combinatorial Optimization, 30(2): 214-241 (2015). Masaki Suzuki, Hiroshi Nagamochi, Tatsuya Akutsu : Efficient enumeration of monocyclic chemical graphs with given path frequencies Journal of Cheminformatics (2014), 6:31 doi:10.1186/1758-2946-6-31 Toshihiro Shimizu, Takuro Fukunaga, Hiroshi Nagamochi : Unranking of small combinations from large sets J. Discrete Algorithms 29: 8-20 (2014) M. Xiao, H. Nagamochi : A refined exact algorithm for Edge Dominating Set Theor. Comput. Sci. 560: 207-216 (2014) Yang Zhao, Morihiro Hayashida, Jira Jindalertudomdee, Hiroshi Nagamochi, Tatsuya Akutsu : Breadth first search approach to enumeration of tree-like chemical compounds Journal of Bioinformatics and Computational Biology (JBCB) No.11, Issue No. 6. (2013) M. Xiao, H. Nagamochi : Parameterized edge dominating set in graphs with degree bounded by 3, Theoretical Computer Science, 508: 2-15 (2013). M. Xiao, H. Nagamochi : Exact algorithms for annotated edge dominating set in graphs with degree bounded by 3, IEICE Transactions, Vol.E96-D No.3 pp.408-418, 2013. A. Shurbevski, H. Nagamochi, Y. Karuno : Better Approximation Algorithms for Grasp-and- Delivery Robot Routing Problems, IEICE Transactions, Vol.E96-D No.3 pp.450-456, 2013. M. Xiao, T. Fukunaga, H. Nagamochi : FPTASs for trimming weighted trees, Theoretical Computer Science 469: 105-118 (2013). M. Xiao, H. Nagamochi : Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs, Theoretical Computer Science 469: 92-104 (2013). Y. Karuno, H. Nagamochi, A. Shurbevski : Constant factor approximation algorithms for repetitive routing problems of grasp-and-delivery robots in production of printed circuit boards, Journal of the Operations Research Society of Japan, 55(3):181-191, 2012. Yang Zhao, Morihiro Hayashida, Jose C. Nacher, Hiroshi Nagamochi, Tatsuya Akutsu : Protein complex prediction via improved verification methods using constrained domain-domain matching, IJBRA 8(3/4): 210-227 (2012) S.-H. Hong, H. Nagamochi : Minimum cost star-shaped drawings of plane graphs with a fixed embedding and concave corner constraints, Theoretical Computer Science 445, 36-51 (2012). Y. Arahori, T. Imamichi, H. Nagamochi : An exact strip packing algorithm based on canonical forms, Computers and Operations Research, Volume 39, Issue 12, December 2012, Pages 2991-3011. T. Imada, H. Nagamochi : Indexing all rooted subgraphs of a rooted graph, IEICE Transactions, 95-D(3): 712-721 (2012). S.-H. Hong H. Nagamochi : A linear-time algorithm for star-shaped drawings of planar graphs with the minimum number of concave corners, Algorithmica, 62: 1122-1158 (2012). K. Okumoto, T. Fukunaga, H. Nagamochi : Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems, Algorithmica, 62:787-806 (2012). M. Xiao, H. Nagamochi : An FPT algorithm for edge subset feedback edge set, Inf. Process. Lett. vol. 112, no. 1-2, pp. 5-9 (2012). H. Aota, T. Fukunaga, H. Nagamochi : An approximation algorithm for locating maximal disks within convex polygons, International Journal of Computational Geometry and Applications (IJCGA) Volume: 21, Issue: 6 (2011) pp. 661-684. S. Imahori, Y. Karuno, H. Nagamochi, X. Wang : Kansei engineering, humans and computers: Efficient dynamic programming algorithms for combinatorial food packing problems, International Journal of Biometrics, 3/3 (2011) 228-245. S. Karakawa, E. Morsy, H. Nagamochi : Minmax tree cover in the Euclidean space, J. Graph Algorithms Appl. 15(3): 345-371 (2011). S.-H. Hong, H. Nagamochi : Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra, Algorithmica 61(4): 1022-1076 (2011). T. Imada, S. Ota, H. Nagamochi, T. Akutsu : Efficient enumeration of stereoisomers of outerplanar chemical graphs using dynamic programming, Journal of Chemical Information and Modeling, Volume 51, Issue 11, pp 2788-2807. November 28, 2011. T. Akutsu, H. Nagamochi : Kernel methods for chemical compounds: from classification to design, IEICE Transactions, Vol. E94-D,No.10, Oct. 2011, 1846-1853. Y. Karuno, H. Nagamochi, A. Shurbevski : An approximation algorithm with factor two for a repetitive routing problem of grasp-and-delivery robots, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.15 No.8, pp. 1103-1108, 2011. K. Matsumoto, S. Umetani, H. Nagamochi : On the one-dimensional stock cutting problem in the paper tube industry, Journal of Scheduling, 14(3): 281-290 (2011). T. Ibaraki, T. Imamichi, Y. Koga, H. Nagamochi, K. Nonobe, M. Yagiura : Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Mathematical Programming A, 127, 2, 297-343 (2011). E. Morsy, H. Nagamochi : Approximating capacitated tree-routings in networks, Journal of Combinatorial Optimization, 21(2) (2011) 254-267. H. Nagamochi : Cop-robber guarding game with cycle robber region, Theoretical Computer Science, 412 (2011) 383-390. E. Morsy, H. Nagamochi : On the approximation of the generalized capacitated tree-routing problem, Journal of Discrete Algorithms, Volume 8, Issue 3, September 2010, Pages 311-320. S. Ota, E. Morsy, H. Nagamochi : A plane graph representation of a triconnected graph, Theoretical Computer Science, 411 (2010) 3979-3993. T. Imada, S. Ota, H. Nagamochi, T. Akutsu : Enumerating stereoisomers of tree structured molecules using dynamic programming, Journal of Mathematical Chemistry, Volume 49, Number 4, 910-970, 2010. Y. Ishida, Y. Kato, L. Zhao, H. Nagamochi, T. Akutsu : Branch-and-bound algorithms for enumerating treelike chemical graphs with given path frequency using detachment-cut, Journal of Chemical Information and Modeling, 50, 934-946, 2010. Y. Karuno, H. Nagamochi, X. Wang : Optimization problems and algorithms in double-layered food packing systems, Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vol. 4, No. 3, 2010, 605-615. T. Fukunaga, H. Nagamochi : Network design with weighted degree constraints, Discrete Optimization, 7 (2010) 246-255. S.-H. Hong, H. Nagamochi : Convex drawings of hierarchical planar graphs and clustered planar graphs, Journal of Discrete Algorithms, 8(3): 282-295 (2010). S.-H. Hong, H. Nagamochi : An algorithm for constructing star-shaped drawings of plane graphs, Computational Geometry Theory and Applications, vol. 43, no. 2, pp. 191-206, February 2010. S.-H. Hong, H. Nagamochi : A linear-time algorithm for symmetric convex drawings of internally triconnected planar graphs, Algorithmica, vol. 58, no. 2, 2010, 433-460. S.-H. Hong, H. Nagamochi : Approximation algorithms for minimizing edge crossings in radial drawings, Algorithmica, vol. 58, no. 2, 2010, 478-497. H. Nagamochi : Minimum degree orderings, Algorithmica, vol. 56, no. 1, 2010, 17-34. T. Ishii, Y. Akiyama, H. Nagamochi : Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs, Algorithmica, vol. 56, no. 4 2010, 413-436. E. Morsy, H. Nagamochi : Approximation to the minimum cost edge installation problem, IEICE Transactions, E93-A, no.4, April 2010, 778-786. S.-H. Hong, H. Nagamochi : New approximation to the radial crossing minimization, Journal of Graph Algorithms and Applications, Vol. 13, no. 2, 179-196, 2009. M. Kenmochi, T. Imamichi, K. Nonobe, M. Yagiura, H. Nagamochi : Exact algorithms for the 2-dimensional strip packing problem with and without rotations, European Journal of Operational Research, 198(1): 73-83 (2009). T. Fukunaga, H. Nagamochi : Eulerian detachment with local edge-connectivity, Discrete Applied Mathematics, 157(4): 691-698 (2009). Y. Karuno, H. Nagamochi, J. Uchida: Selective vehicle scheduling on paths with a due date involving criterion, Transactions of the Japan Society of Mechanical Engineers, Series C, vol. 73, no. 727, pp.911-918 (2007). T. Imamichi, M. Yagiura, H. Nagamochi : An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem, Discrete Optimization, vol. 6, no. 4, pp. 345-361, November 2009. T. Fukunaga, H. Nagamochi : Network design with edge-connectivity and degree constraints, Theory of Computing Systems, vol. 45, no. 3, pp. 512-532 (2009). M. Sakashita, K. Makino, H. Nagamochi, S. Fujishige : Minimum transversals in posi-modular systems, SIAM J. Disc. Math. Volume 23, Issue 2, pp. 858-871 (2009) A. Kawaguchi, H. Nagamochi : Drawing slicing graphs with face areas, Theoretical Computer Science, 410(11): 1061-1072 (2009). H. Nagamochi : A detachment algorithm for inferring a graph from path frequency, Algorithmica, 53(2): 207-224 (2009). J. Uchida, Y. Karuno, H. Nagamochi : Scheduling capacitated one-way vehicles on paths with deadlines, SICE Journal of Control, Measurement, and System Integration Vol. 2, No. 1, January 2009, pp. 20-26. T. Imamichi, H. Nagamochi : Performance analysis of a collision detection algorithm of spheres based on slab partitioning, IEICE Transactions 91-A(9): 2308-2313 (2008). H. Fujiwara, J. Wang, L. Zhao, H. Nagamochi, T. Akutsu : Enumerating tree-like chemical graphs with given path frequency, Journal of Chemical Information and Modeling, 48 1345-1357, 2008. Y. Nakao, H. Nagamochi : Worst case analysis for pickup and delivery problems with transfer, IEICE Transactions 91-A(9): 2328-2334 (2008). S.-H. Hong, H. Nagamochi : Convex drawings of graphs with non-convex boundary constraints, Discrete Applied Mathematics, 156 (2008) 2368-2380. H. Nagamochi, T. Ohnishi : Approximating a vehicle scheduling problem with time windows and handling times, Theoretical Computer Science, 393 (1-3): 133-146 (2008). M. Hayashida, T. Akutsu, H. Nagamochi : A clustering method for analysis of sequence similarity networks of proteins using maximal components of graphs, IPSJ Transactions on Bioinformatics, 49-Sig 5 (TBIO 4), 15-24, 2008. E. Morsy, H. Nagamochi : An improved approximation algorithm for capacitated multicast routings in networks, Theoretical Computer Science, vol. 390(1): 81-91, 2008. H. Fujita, T. Ishii, H. Nagamochi : The source location problem with local 3-vertex-connectivity requirements, Discrete Applied Mathematics, vol. 155, no. 18, pp. 2523-2538, 2007. Y. Karuno, H. Nagamochi, X. Wang : Bi-criteria food packing by dynamic programming, J. Operations Research Society of Japan, vol. 50, no. 4, pp. 376-389, 2007. T. Fukunaga, H. Nagamochi: Approximating minimum cost multigraphs of specified edge-connectivity under degree bounds, J. Operations Research Society of Japan, vol. 50, no. 4, pp. 339-349, 2007. A. Berger, T. Fukunaga, H. Nagamochi, O. Parekh : Approximability of the capacitated b-edge dominating set problem, Theoretical Computer Science A, vol. 385, pp. 202-213, 2007. K. Hirata, T. Matsuda, H. Nagamochi, T. Takine : Contention-free \lambda-planes in optically burst-switched WDM networks, IEICE Transactions on Communications, vol.E90-B, no.9, pp.2524-2531, 2007. T. Fukunaga, H. Nagamochi: Approximating a generalization of metric TSP, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol.E90-D, no.2, pp.432-439, 2007. H. Nagamochi: Computing a minimum cut in a graph with dynamic edges incident to a designated vertex, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals vol.E90-D, no.2, pp.428-431, 2007. H. Nagamochi, K. Okada: Approximating the minmax rooted-tree cover in a tree, Information Processing Letters, vol. 104, pp. 173-178, 2007. T. Ishii, K. Iwata, H. Nagamochi: Bisecting a four-connected graph with three resource sets, Discrete Applied Mathematics, vol. 155, pp. 1441-1450, 2007. Y. Nakao, H. Nagamochi: A DP-based heuristic algorithm for the discrete split delivery vehicle routing problem, Journal of Advanced Mechanical Design, Systems, and Manufacturing, vol. 1, no. 2, pp.217-226, 2007. T. Fukunaga, H. Nagamochi: Generalizing the induced matching by edge capacity constraints, Discrete Optimization, vol. 4, no. 2, pp. 198-205, June 2007. T. Ishii, H. Fujita, H. Nagamochi: Minimum cost source location problem with local 3-vertex-connectivity requirements, Theoretical Computer Science, vol. 372(1) pp. 81-93, 2007. E. Morsy, H. Nagamochi: Approximation algorithms for multicast routings in a network with multi-sources, IEICE Transactions vol. E90-A, no. 5, pp. 900-906, 2007. H. Nagamochi, K. Kuroya : Drawing c-planar biconnected clustered graphs, Discrete Applied Mathematics, vol.155, pp. 1155-1174, 2007. H. Nagamochi, Y. Kamidoi: Minimum cost subpartitions in graphs, Information Processing Letters, vol. 102, 2007, pp. 79-84, 2007. H. Nagamochi, Y. Abe: An approximation algorithm for dissecting a rectangle into rectangles with specified areas, Discrete Applied Mathematics, vol. 155, pp. 523-537, 2007. Y. Kamidoi, N. Yoshida, H. Nagamochi: A deterministic algorithm for finding all minimum k-way cuts, SIAM J. Computing, vol. 36, no. 5, 2006, pp. 943-955. H. Nagamochi: Packing soft rectangles, International Journal of Foundations of Computer Science, vol. 17, no. 5, 2006, pp. 1165-1178. H. Ito, H. Nagamochi : Two equivalent measures on weighted hypergraphs, Discrete Applied Mathematics, vol. 154, 2006, pp. 2330-2334. H. Nagamochi : Sparse connectivity certificates via MA orderings in graphs, Discrete Applied Mathematics, vol. 154, 2006, pp. 2411-2417. T. Ishii, S. Yamamoto, H. Nagamochi: Augmenting forests to meet odd diameter requirements, Discrete Optimization, vol. 3, no. 2, 2006, pp. 154-164. H. Nagamochi: A fast edge-splitting algorithm in edge-weighted graphs, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol. E89-A, no. 5, May 2006, pp. 1263-1268. Y. Karuno, H. Nagamochi, Y. Ohshima: A dynamic programming approach for a food packing problem (in Japanese), Transactions of the Japan Society of Mechanical Engineers, Series C, vol. 72, no. 716, 2006, pp. 1390-1397. H. Nagamochi, T. Kawada: Minmax subtree cover problem on cacti, Discrete Applied Mathematics, vol. 154, no. 8, 2006, pp. 1254-1263. T. Ishii, H. Nagamochi, T. Ibaraki: Augmenting a (k-1)-vertex-connected multigraph to an l-edge-connected and k-vertex-connected multigraph, Algorithmica, vol. 44, no. 3, 2006, pp. 257-280. H. Nagamochi : Increasing the edge-connectivity by contracting a vertex subset, IEICE Transactions on Information and Systems, vol. E89-D, no. 2, Feb. 2006, pp. 744-750. P. Eades, Q. Feng, X. Lin, H. Nagamochi: Straight-line drawing algorithms for hierarchical graphs, and clustered graphs, Algorithmica, vol. 44, no. 1, 2006, pp. 1-32. Y. Karuno, H. Nagamochi: Scheduling vehicles on trees, Pacific Journal of Optimization, vol. 1, 2005, pp. 527-543. H. Nagamochi, K. Iwata, T. Ishii : A robust algorithm for bisecting a triconnected graph with two resource sets, Theoretical Computer Science A, vol. 341, 2005, pp. 364-378 H. Nagamochi: A 4/3-approximation for the minimum 2-local-vertex-connectivity augmentation in a connected graph, J. Algorithms, vol. 56, 2005, pp. 77-95. H. Nagamochi : Packing unit squares in a rectangle, The Electronic Journal of Combinatorics, R37, vol.12(1), 2005. T. Ishii, H. Nagamochi, Y. Nishigaki, K. Takahashi, M. Takeda : A routing algorithm on a storage tank system (in Japanese), ISCIE Journal Systems, Control and Information, vol. 18, no. 6, 2005, pp. 213-221. H. Nagamochi: Approximating the minmax rooted-subtree cover problem, Electron. Inform. Comm. Eng. Trans. Fundamentals, vol. E88-A, no. 5, May, 2005, pp. 1335-1338. H. Nagamochi: An improved bound on the one-sided minimum crossing number in two-layered drawings, Discrete and Computational Geometry, vol. 33, 2005, pp. 569-591. H. Nagamochi: On the one-sided crossing minimization in a bipartite graph with large degrees, Theoretical Computer Science A, vol. 332, 2005, pp. 417-446. H. Nagamochi: On computing minimum (s,t)-cuts in digraphs, Information Processing Letters, vol. 93, no 5, 2005, pp. 231-237. L. Zhao, H. Nagamochi, T. Ibaraki: A greedy splitting algorithm for approximating multiway partition problems, Mathematical Programming, vol. 102, no. 1, 2005, pp. 67-183. H. Nagamochi: On 2-approximation to the vertex-connectivity in graphs, Inst. Electron. Inform. Comm. Eng. Trans. Information and Systems, vol. E88-D, no.1, 2005, pp. 12-16. H. Nagamochi: Graph algorithms for network connectivity problems, J. Operations Research Society of Japan, vol.47, no.4, 2004, pp. 199-223. H. Nagamochi, N. Yamada: Counting edge crossings in a 2-layered drawing, Information Processing Letters, vol. 91, 2004, pp. 221-225. L. Zhao, H. Nagamochi, T. Ibaraki: On generalized greedy splitting algorithms for multiway partition problems, Discrete Applied Mathematics, vol. 143, no.1, 2004, pp. 130-143. H. Nagamochi, K. Okada: A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree, Discrete Applied Mathematics, vol.140, no. 1-3, 2004, pp. 103-114. H. Nagamochi, K. Suzuki, T. Ishii: A simple recognition of maximal planar graphs, Information Processing Letters, vol.89, no.5, 2004, pp. 223-226. Y. Karuno, H. Nagamochi: An approximability result of the multi-vehicle scheduling problem on a path with release and handling times, Theoretical Computer Science A, vol.312, issues 2-3, 2004, pp. 267-280. H. Nagamochi, Y. Nishida, T. Ibaraki: Approximability of the minimum maximal matching problem in planar graphs, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol.E86-A, 2003, pp. 3251-3258. H. Nagamochi, P. Eades: An edge-splitting algorithm in planar graphs, J. Combinatorial Optimization, vol.7, 2003, pp. 137-159. H. Nagamochi, T. Ishii: On the minimum local-vertex-connectivity augmentation in graphs, Discrete Applied Mathematics, vol.129/2, 2003, pp. 475-486. Y. Karuno, H. Nagamochi: 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times, Discrete Applied Mathematics, vol.129/2, 2003, pp. 433-447. L. Zhao, H. Nagamochi, T. Ibaraki: A linear time 5/3-approximation for the minimum strongly-connected spanning subgraph problem, Information Processing Letters, vol.86/2, 2003, pp. 63-70. H. Nagamochi, S. Nakamura, T. Ishii: Constructing a cactus for minimum cuts of a graph in O(mn+n^2 log n) time and O(m) space, Inst. Electron. Inform. Comm. Eng. Trans. Information and Systems, vol.E86-D, no.2, 2003, pp. 179-185. H. Nagamochi: Algorithms for the minimum partitioning problems in graphs (in Japanese), Inst. Electron. Inform. Comm. Eng. Trans. Information and Systems, vol. J86-D-I, no.2, 2003, pp. 53-68. H. Nagamochi, T. Jordan, Y. Nakao, T. Ibaraki: Bisecting two subsets in 3-connected graphs, Combinatorica, vol.22, no.4, 2002, pp. 537-554. L. Zhao, H. Nagamochi, T. Ibaraki: A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Discrete Applied Mathematics, vol. 126/2-3, 2002, pp. 275-289. H. Nagamochi: An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree, Discrete Applied Mathematics, vol. 126, no.1, 2002, pp. 83-113. Y. Karuno, H. Nagamochi, T. Ibaraki: Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks, Networks , vol. 39, no. 4, 2002, pp. 203-209. L. Zhao, H. Nagamochi, T. Ibaraki: A note on approximating the survivable network design problem in hypergraphs, Inst. Electron. Inform. Comm. Eng. Trans. Information and Systems, vol.E85-D, no.2, Feb. 2002, pp.322-326. H. Nagamochi, T. Ibaraki: Graph connectivity and its augmentation: applications of MA orderings, Discrete Applied Mathematics, vol.123, no.1, 2002, pp. 447-472. T. Fujito, H. Nagamochi: A 2-approximation algorithm for the minimum weight edge dominating set problem, Discrete Applied Mathematics, vol.118, no.3, 2002, pp.199-208. H. Nagamochi, T. Shiraki, T. Ibaraki: Augmenting a submodular and posi-modular set function by a multigraph, J. Combinatorial Optimization, vol.5, no.2, 2001, pp.175-212. H. Nagamochi, T. Hasunuma: An efficient NC algorithm for a sparse k-edge-connectivity certificate, J. Algorithms, vol.38, no.2, 2001, pp.354-373. H. Nagamochi, K. Mochizuki, T. Ibaraki: Solving the single-vehicle scheduling problem for all home locations under depth-first routing on a tree, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol.E84-A, no.5, May 2001, pp.1135-1143. T. Ishii, H. Nagamochi, T. Ibaraki: Multigraph augmentation under biconnectivity and general edge-connectivity requirements, Networks, vol.37, no. 3, 2001, pp.144-155. L. Zhao, H. Nagamochi, T. Ibaraki: Approximating the minimum k-way cut in a graph via minimum 3-way cuts, J. Combinatorial Optimization, vol.5, 2001, pp.397-410. T. Hasunuma, H. Nagamochi: Independent spanning trees with small depths in iterated line digraphs, Discrete Applied Mathematics, vol.110, no.2, 2001, pp.189-212. H. Nagamochi, T. Ishii, H. Ito: Minimum cost source location problem with vertex-connectivity requirements in digraphs, Information Processing Letters, vol.80, no.6, 2001, pp. 287-294. H. Nagamochi, M. Miller, Slamin: Bounds on sum number in graphs, Discrete Mathematics, vol.240, no.1-3, 2001, pp.175-185. H. Nagamochi, S. Nakamura, T. Ibaraki: A simplified O(nm) time edge-splitting algorithm, Algorithmica, vol.26, 2000, pp.50-57. T. Ishii, H. Nagamochi, T. Ibaraki: Optimal augmentation of a 2-vertex-connected multigraph to a k-edge-connected and 3-vertex-connected multigraph, J. Combinatorial Optimization, vol.4, 2000, pp.35-78. H. Nagamochi: Recent development of graph connectivity augmentation algorithms, Inst. Electron. Inform. Comm. Eng. Trans. Information and Systems, vol.E83-D, no.3, March 2000, pp.372-383. H. Nagamochi, K. Seki, T. Ibaraki: A 7/3 approximation for the minimum weight 3-connected spanning subgraph problem, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol.E83-A, no.4, April 2000, pp.687-691. H. Nagamochi, S. Katayama, T. Ibaraki: Faster algorithm for computing minimum 5-way and 6-way cuts, J. Combinatorial Optimization, vol.4, 2000, pp.151-169. H. Nagamochi, Y. Nakao, T. Ibaraki: A fast algorithm for cactus representations of minimum cuts, J. of Japan Society for Industrial and Applied Mathematics vol.17, 2000, pp. 245-264. X. Deng, T. Ibaraki, H. Nagamochi, W. Zang: Totally balanced combinatorial optimization games, Mathematical Programming, vol.87, no.3, 2000, pp.441-452. H. Nagamochi, T. Ibaraki: A fast algorithm for computing minimum 3-way and 4-way cuts, Mathematical Programming, vol.88, no.3, 2000, pp.507-520. H. Nagamochi, T. Ibaraki: Polyhedral structure of submodular and posi-modular systems, Discrete Applied Mathematics, vol.107, 2000, pp.165-189. H. Nagamochi, T. Ibaraki: Augmenting edge-connectivity over the entire range in O(nm) time, Journal of Algorithms, vol.30, 1999, pp.253-301. H. Nagamochi, T. Ibaraki: An approximation of the minimum vertex cover in a graph, J. of Japan Society for Industrial and Applied Mathematics, vol.16, no.3, 1999, pp.369-375. X. Deng, T. Ibaraki, H. Nagamochi: Algorithmic aspects of the core of combinatorial optimization games, Math. of Operations Research, vol.24, no.3, August 1999, pp.751-766. H. Nagamochi, T. Ishii, T. Ibaraki: A simple proof of a minimum cut algorithm and its applications, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol.E82-A, no.10, Oct. 1999, pp.2231-2236. P. Eades, Q. Feng, H. Nagamochi: Drawing clustered graphs on an orthogonal grid, Journal of Graph Algorithms and Application, vol.3, no.4, 1999, pp.3-29. H. Nagamochi, K. Makino, D.-Z. Zeng, M. Murata, T. Ibaraki: Convexity of elementary flow game (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap. vol.J81-D-I, no.6, 1998, pp.666-676. A. Frank, T. Ibaraki, H. Nagamochi: Two arc-disjoint paths in Eulerian digraphs, SIAM Disc. Math., vol.11, no.4, 1998, pp.557-589. T. Ibaraki, A. Karzanov, H. Nagamochi: A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizations, Combinatorica, vol.18, no.1, 1998, pp.61-83. H. Nagamochi, T. Ibaraki: A note on minimizing submodular functions, Information Processing Letters, vol.67, 1998, pp.239-244. M. Kato, R. Kawakita, H. Nagamochi, Y. Oie: On a reconfiguration algorithm for torus lightwave networks (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J80-B-I, no.10, Oct. 1997, pp.709-718. Y. Karuno, H. Nagamochi, T. Ibaraki: Vehicle scheduling on a tree with release and handling times, Annals of Operation Research,vol. 69, 1997, pp.193-207. H. Nagamochi, K. Nishimura, T. Ibaraki: Computing all small cuts in undirected networks, SIAM Disc. Math. vol.10, no.3, 1997, pp.469-481. H. Nagamochi, T. Ibaraki: Deterministic O(nm) time edge-splitting in undirected graphs, J. Combinatorial Optimization, vol.1, no.1, 1997, pp.5-46. H. Nagamochi, K. Mochizuki, T. Ibaraki: Complexity of the single vehicle scheduling problem on graphs, Information Systems and Operations Research, vol.35, no.4, 1997, pp.256-276. Y. Karuno, H. Nagamochi, T. Ibaraki: Computational complexity of the traveling salesman problem on a line with deadlines and general handling times, Memories of the Faculty of Engineering and Design, Kyoto Institute of Technology, vol.45, 1997, pp.19-22. H. Nagamochi, D.-Z. Zeng, N. Kabutoya, T. Ibaraki: Complexity of the minimum base game on matroids, Mathematics of Operations Research, vol.22, no.1, 1997, pp.146-164. H. Nagamochi, T. Kameda: Constructing cactus representation for all minimum cuts in an undirected network, Operations Research Society of Japan, vol.39, no.2, 1996, pp.135-158. Y. Karuno, H. Nagamochi, T. Ibaraki: Vehicle scheduling on a tree to minimize maximum lateness, Operations Research Society of Japan, vol.39, no.3, 1996, pp.345-355. M. Yagiura, H. Nagamochi, T. Ibaraki: Two comments on the subtour exchange crossover operator (in Japanese), Journal of Japanese Society for Artificial Intelligence, vol.10, no.3, 1995, pp.464-467. T. Ibaraki, H. Nagamochi, T. Kameda: Optimal coteries for rings and related networks, Distributed Computing, vol.8, no.4, 1995, pp.191-201. H. Nagamochi, T. Kameda: Canonical cactus representation for minimum cuts, J. of Japan Society for Industrial and Applied Mathematics, vol.11, no.3, 1994, pp.343-361. H. Harada, Z. Sun, H. Nagamochi: An exact lower bound on the number of cut-sets in multigraphs, Networks, vol.24, 1994, pp.429-443. H. Nagamochi, T. Ono, T. Ibaraki: Implementing an efficient minimum capacity cut algorithm, Mathematical Programming, vol.67, 1994, pp.325-341. A. Frank, T. Ibaraki, H. Nagamochi: On sparse subgraph preserving connectivity properties, J. Graph Theory, vol.17, no.3, July 1993, pp.275-281. H. Nagamochi, T. Watanabe: Computing k-edge-connected components in multigraphs, Inst. Electron. Inform. Comm. Eng. Trans. Fundamentals, vol.E76-A, no.4, 1993, pp.513-517. H. Nagamochi, T. Ibaraki: Computing the edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics vol.5, 1992, pp.54-66. H. Nagamochi, T. Ibaraki: A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica vol.7, 1992, pp.583-596. H. Nagamochi, T. Ibaraki: On Onaga's upper bound on the mean values of probabilistic maximum flows, IEEE Trans. on Reliability, vol.41, 1992, pp.225-229. H. Nagamochi, T. Ibaraki: A linear time algorithm for computing 3-edge-connected components in multigraphs, J. of Japan Society for Industrial and Applied Mathematics, vol.9, no.2, 1992, pp.163-180. H. Nagamochi, T. Ibaraki: Maximum flows in probabilistic networks, Networks, vol.21, no.6, 1991, pp.645-666. H. Nagamochi, Z. Sun, T. Ibaraki: Counting the number of minimum cuts in undirected multigraphs, IEEE Trans. on Reliability, vol.40, 1991, pp.610-614. H. Nagamochi, T. Ibaraki: Multicommodity flows in certain planar directed networks, Discrete Applied Mathematics, vol.27, 1990, pp.125-145. H. Nagamochi, M. Fukushima, T. Ibaraki: Relaxation methods for the strictly convex multicommodity flow problem with capacity constraints on individual commodities, Networks, vol.20, 1990, pp.409-426. Z. Sun, H. Nagamochi, K. Kusunoki: 2-edge-connected graphs minimizing the number of cut-sets with 3 edges (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J73-A, no.7, 1990, pp.1281-1285. Z. Sun, H. Nagamochi, K. Kusunoki: A multiple graph minimizing the number of minimum cut sets, Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.E73, no.6, 1990, pp.915-921. Z. Sun, H. Nagamochi, K. Kusunoki: A graph minimizing the number of cut-sets with a specified number of edges (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J72-A, no.10, 1989, pp.1601-1611. H. Nagamochi, K. Chiba, K. Kusunoki: On the expected maximum flows in probabilistic networks (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J72-A, no.10, 1989, pp.1611-1620. H. Nagamochi, T. Ibaraki: On max-flow min-cut and integral flow properties for multicommodity flow in directed networks, Information Processing Letters, vol.31, 1989, pp.279-285. H. Nagamochi, T. Ibaraki: An efficient feasibility testing of the multicommodity flow problem in certain planar directed networks (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J71-A, no.3, 1988, pp.804-810. H. Nagamochi, T. Ibaraki: Max-flow min-cut theorem for the multicommodity flow in certain planar directed networks (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J71-A, no.1, 1988, pp 71-82 [Eng. transl. Electronics and Communications in Japan, Scripta Technica, Inc. vol.72, no.3, 1989, pp.58-72]. H. Nagamochi, T. Ibaraki, T. Hasegawa: Multicommodity flow problem for class CU of planar directed networks (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J70-A, no.9, 1987, pp.1328-1339. H. Nagamochi, T. Ibaraki, T. Hasegawa: Multicommodity flow problem in certain planar directed networks (in Japanese), Trans. Inst. Electron. Inform. Comm. Eng. Jap., vol.J70-A, no.2, 1987, pp.228-238.

International Conference Papers

Books

Dissertation

H. Nagamochi: Studies on Multicommodity Flows in Directed Networks, Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, 1988. [Download(PDF)]

HOME(Japanese) HOME(English)
TECHNICAL REPORTS (Department of Applied Mathematics and Physics) -->