Nagamochi Hiroshi

Hiroshi Nagamochi

Information about the author Hiroshi Nagamochi will soon be added to the site.
Found 19 papers in total
Divide‐and‐Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
Divide‐and‐Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
2012
The submodular system k ‐partition problem is a problem of partitioning a given...
A Linear‐Time Algorithm for Star‐Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners
A Linear‐Time Algorithm for Star‐Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners
2012
A star‐shaped drawing of a graph is a straight‐line drawing such that...
Extending Steinitz’s Theorem to Upward Star‐Shaped Polyhedra and Spherical Polyhedra
Extending Steinitz’s Theorem to Upward Star‐Shaped Polyhedra and Spherical Polyhedra
2011
In 1922, Steinitz’s theorem gave a complete characterization of the topological...
Approximating capacitated tree‐routings in networks
Approximating capacitated tree‐routings in networks
2011
Let G =( V , E ) be a connected graph such that each edge e ∈ E is weighted by a...
On the one‐dimensional stock cutting problem in the paper tube industry
On the one‐dimensional stock cutting problem in the paper tube industry
2011
The one‐dimensional cutting stock problem (1D‐CSP) is one of the...
Approximating minimum cost multigraphs of specified edge-connectivity under degree bounds
Approximating minimum cost multigraphs of specified edge-connectivity under degree bounds
2007
In this paper, we consider the problem of constructing a minimum cost graph with a...
Bi-criteria food packing by dynamic programming
Bi-criteria food packing by dynamic programming
2007
In this paper, we deal with a certain type of automated food packing system with n...
Graph algorithms for network connectivity problems
Graph algorithms for network connectivity problems
2004
This paper surveys the recent progress on the graph algorithms for solving network...
Complexity of the minimum base game on matroids
Complexity of the minimum base game on matroids
1997
This paper studies the complexity of computing solution concepts for a cooperative...
Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
2002
We consider two variants of the single-vehicle scheduling problem on line-shaped...
A simple proof of a minimum cut algorithm and its applications
A simple proof of a minimum cut algorithm and its applications
1999
For the correctness of the minimum cut algorithm proposed by Nagamochi and Ibaraki,...
Complexity of the single vehicle scheduling problem on graphs
Complexity of the single vehicle scheduling problem on graphs
1997
Let G = ( V , E ) be a graph. The travel times w ( u , v ) and w ( v , u ) are...
Vehicle scheduling on a tree with release and handling times
Vehicle scheduling on a tree with release and handling times
1997
In this paper, the authors consider a single-vehicle scheduling problem on a...
Vehicle scheduling on a tree to minimize maximum lateness
Vehicle scheduling on a tree to minimize maximum lateness
1996
In this paper the authors deal with a single-vehicle scheduling problem on a...
Constructing a cactus representation for all minimum cuts in an undirected network
Constructing a cactus representation for all minimum cuts in an undirected network
1996
The construction of a cactus representation for all minimum cuts in an edge-weighted,...
Implementing an efficient minimum capacity cut algorithm
Implementing an efficient minimum capacity cut algorithm
1994
In this paper, the authors present an efficient implementation for the O(mn+n 2...
A graph minimizing the number of cut-sets with a specified number of edges
A graph minimizing the number of cut-sets with a specified number of edges
1989
A graph G with n nodes and e edges maximizing the edge-connectivity λ (i.e.,...
On the expected maximum flow in probabilistic networks
On the expected maximum flow in probabilistic networks
1989
The reliability of capacitated networ
On max-flow min-cut and integral flow properties for multocommodity flows in directed networks
On max-flow min-cut and integral flow properties for multocommodity flows in directed networks
1989
The multicommodity flow problem can represent many important problems encountered in a...
Papers per page: