Hiroshi NAGAMOCHI


An Exact Algorithm for Lowest Edge Dominating Set
Ken IWAIDE Hiroshi NAGAMOCHI 
Publication:   
Publication Date: 2017/03/01
Vol. E100-D  No. 3  pp. 414-421
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Theoretical Computer Science —)
Category: 
Keyword: 
graph theoryedge dominating setalgorithmNP-completenessfixed parameter tractable
 Summary | Full Text:PDF(304.7KB)

Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees
Morito OOMINE Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/03/01
Vol. E99-D  No. 3  pp. 615-623
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
Category: 
Keyword: 
mechanismsgroup strategy-prooffacility location gamestrees
 Summary | Full Text:PDF(349KB)

Some Reduction Procedure for Computing Pathwidth of Undirected Graphs
Masataka IKEDA Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Vol. E98-D  No. 3  pp. 503-511
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
pathwidthexact algorithmsgraphschemical graphs
 Summary | Full Text:PDF(1MB)

Exact Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3
Mingyu XIAO Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3  pp. 408-418
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
edge dominating setsexact algorithmscubic graphs
 Summary | Full Text:PDF(337.9KB)

Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI Yoshiyuki KARUNO 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3  pp. 450-456
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
combinatorial optimizationrouting and schedulingindustrial robotsapproximation algorithmsmetric traveling salesperson problem
 Summary | Full Text:PDF(261.4KB)

Indexing All Rooted Subgraphs of a Rooted Graph
Tomoki IMADA Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2012/03/01
Vol. E95-D  No. 3  pp. 712-721
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science – Mathematical Foundations and Applications of Computer Science and Algorithms –)
Category: 
Keyword: 
graph isomorphismindexrooted graphsouterplanar graphssignature
 Summary | Full Text:PDF(228KB)

Kernel Methods for Chemical Compounds: From Classification to Design
Tatsuya AKUTSU Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/10/01
Vol. E94-D  No. 10  pp. 1846-1853
Type of Manuscript:  INVITED PAPER (Special Section on Information-Based Induction Sciences and Machine Learning)
Category: 
Keyword: 
chemoinformaticskernel methodpre-imagedynamic programmingenumerationgraph detachment
 Summary | Full Text:PDF(457.5KB)

Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
Bingbing ZHUANG Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/02/01
Vol. E94-D  No. 2  pp. 200-210
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
enumerationreflective symmetrytriangulationplane graphsplanar graphsbiconnectivitygraph algorithms
 Summary | Full Text:PDF(886.5KB)

Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
Bingbing ZHUANG Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2011/02/01
Vol. E94-D  No. 2  pp. 211-219
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
Category: 
Keyword: 
enumeration algorithmgraph algorithmplanar graphouterplanar graphsymmetry
 Summary | Full Text:PDF(722.6KB)

Approximation to the Minimum Cost Edge Installation Problem
Ehab MORSY Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2010/04/01
Vol. E93-A  No. 4  pp. 778-786
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
approximation algorithmgraph algorithmrouting problemnetwork optimization
 Summary | Full Text:PDF(250KB)

Worst Case Analysis for Pickup and Delivery Problems with Transfer
Yoshitaka NAKAO Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/09/01
Vol. E91-A  No. 9  pp. 2328-2334
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
pickup and delivery problemtransshipmentupper bound
 Summary | Full Text:PDF(260.4KB)

Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
Takashi IMAMICHI Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2008/09/01
Vol. E91-A  No. 9  pp. 2308-2313
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
collision detectionslab partitioningplane sweep methodpolynomial algorithmcomputational geometry
 Summary | Full Text:PDF(178.2KB)

Contention-Free λ-Planes in Optically Burst-Switched WDM Networks
Kouji HIRATA Takahiro MATSUDA Hiroshi NAGAMOCHI Tetsuya TAKINE 
Publication:   IEICE TRANSACTIONS on Communications
Publication Date: 2007/09/01
Vol. E90-B  No. 9  pp. 2524-2531
Type of Manuscript:  PAPER
Category: Internet
Keyword: 
optical burst switchingWDMwavelength assignmentburst scheduling
 Summary | Full Text:PDF(1015KB)

Approximation Algorithms for Multicast Routings in a Network with Multi-Sources
Ehab MOSRY Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2007/05/01
Vol. E90-A  No. 5  pp. 900-906
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
approximation algorithmfacility location problemgraph algorithmmulticast routing problemnetwork optimizationtree cover
 Summary | Full Text:PDF(195.1KB)

Approximating a Generalization of Metric TSP
Takuro FUKUNAGA Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/02/01
Vol. E90-D  No. 2  pp. 432-439
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
approximation algorithmedge-connectivitydegree specificationgraph algorithmmetricnetwork designTSP
 Summary | Full Text:PDF(376.3KB)

Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2007/02/01
Vol. E90-D  No. 2  pp. 428-431
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
dynamic graphedge-connectivityextreme vertex setgraph algorithm
 Summary | Full Text:PDF(153.4KB)

A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5  pp. 1263-1268
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithmconnectivity augmentationedge-connectivityedge-splittingextreme vertex setsgraph
 Summary | Full Text:PDF(166.6KB)

Increasing the Edge-Connectivity by Contracting a Vertex Subset in Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/02/01
Vol. E89-D  No. 2  pp. 744-750
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
algorithmedge-connectivityextreme vertex setsgraphsource location problem
 Summary | Full Text:PDF(532.5KB)

Approximating the Minmax Rooted-Subtree Cover Problem
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Vol. E88-A  No. 5  pp. 1335-1338
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
approximation algorithmgraph algorithmpartitionsubtree cover problemtraveling salesman problem
 Summary | Full Text:PDF(100.8KB)

On 2-Approximation to the Vertex-Connectivity in Graphs
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2005/01/01
Vol. E88-D  No. 1  pp. 12-16
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
graph algorithmapproximation algorithmvertex-connectivityMA orderingsminimum degree
 Summary | Full Text:PDF(128.7KB)

Approximability of the Minimum Maximal Matching Problem in Planar Graphs
Hiroshi NAGAMOCHI Yukihiro NISHIDA Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/12/01
Vol. E86-A  No. 12  pp. 3251-3258
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
graph algorithmapproximation algorithmmatchingplanar graphseparator
 Summary | Full Text:PDF(259.3KB)

Constructing a Cactus for Minimum Cuts of a Graph in O(mn+n2log n) Time and O(m) Space
Hiroshi NAGAMOCHI Shuji NAKAMURA Toshimasa ISHII 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/02/01
Vol. E86-D  No. 2  pp. 179-185
Type of Manuscript:  Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: Graph Algorithms
Keyword: 
graphminimum cutalgorithmcactusmaximum adjacency orderingconnectivitymaximum flow
 Summary | Full Text:PDF(280.3KB)

A Note on Approximating the Survivable Network Design Problem in Hypergraphs
Liang ZHAO Hiroshi NAGAMOCHI Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Vol. E85-D  No. 2  pp. 322-326
Type of Manuscript:  Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
survivable network design problemapproximation algorithmconnectivitygraphhypergraph
 Summary | Full Text:PDF(368.9KB)

Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree
Hiroshi NAGAMOCHI Koji MOCHIZUKI Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/05/01
Vol. E84-A  No. 5  pp. 1135-1143
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
vehicle-schedulingtreealgorithmlocation problem
 Summary | Full Text:PDF(267KB)

A 7/3-Approximation for the Minimum Weight 3-Connected Spanning Subgraph Problem
Hiroshi NAGAMOCHI Katsuhiro SEKI Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Vol. E83-A  No. 4  pp. 687-691
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
undirected graphvertex-connectivityapproximation algorithmspanning subgraph
 Summary | Full Text:PDF(392.2KB)

Recent Development of Graph Connectivity Augmentation Algorithms
Hiroshi NAGAMOCHI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Vol. E83-D  No. 3  pp. 372-383
Type of Manuscript:  INVITED SURVEY PAPER
Category: Graph Algorithms
Keyword: 
edge-connectivityvertex-connectivityminimum cutsgraphsaugmentation problempolynomial algorithm
 Summary | Full Text:PDF(396.2KB)

A Simple Proof of a Minimum Cut Algorithm and Its Applications
Hiroshi NAGAMOCHI Toshimasa ISHII Toshihide IBARAKI 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/10/25
Vol. E82-A  No. 10  pp. 2231-2236
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
graphedge-connectivityminimum cutflowMA-orderingdynamic tree structure
 Summary | Full Text:PDF(406.5KB)

Computing k-Edge-Connected Components of a Multigraph
Hiroshi NAGAMOCHI Toshimasa WATANABE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/04/25
Vol. E76-A  No. 4  pp. 513-517
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design of algorithm, computational complexitymultigraphsedge-connectivityconnected componetsmaximum flowsminimum cutspolynomial-time algorithms
 Summary | Full Text:PDF(437.9KB)

Multiple Graphs Minimizing the Number of Minimum Cut-Sets
Zheng SUN Hiroshi NAGAMOCHI Kikunobu KUSUNOKI 
Publication:   IEICE TRANSACTIONS (1976-1990)
Publication Date: 1990/06/25
Vol. E73-E  No. 6  pp. 915-921
Type of Manuscript:  PAPER
Category: Graphs and Networks
Keyword: 
 Summary | Full Text:PDF(545.8KB)