Arrow Research search

Author name cluster

Naoki Katoh

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

TCS Journal 2025 Journal Article

Constructing red-black spanners for mixed-charging vehicular networks

  • Sergey Bereg
  • Yuya Higashikawa
  • Naoki Katoh
  • Junichi Teruyama
  • Yuki Tokuni
  • Binhai Zhu

Motivated by the recent trend of increasing number of e-cars and hybrid cars, we investigate the problem of building a red-black spanner for a mixed-charging vehicular network. In such a network, we have two kinds of gas/charging stations: electric (black) and the traditional gas (red) stations. Our requirement is that one cannot connect two gas stations directly in the spanner (i. e. , no red-red edge), and the goal is to build a linear-size spanner with a bounded stretch factor under this requirement. (In 2-d, it can be shown that a spanner with an optimal stretch factor could have a quadratic size and if one is constrained to build the spanner purely from a given road network then it is impossible to obtain a bounded stretch factor.) Our main results are summarized as follows. 1. In 1-d, a linear-size red-black spanner is built to satisfy the ‘no red-red edge’ requirement which achieves the optimal stretch factor. 2. In 2-d and under the L 2 metric, we build a linear-size red-black spanner satisfying the ‘no red-red edge’ requirement which achieves a stretch factor of 1. 998. 3. In 2-d and under the L 1 metric, a linear-size red-black spanner is built to satisfy the ‘no red-red edge’ requirement which achieves a stretch factor of 3. 613.

Details DOI

TCS Journal 2025 Journal Article

Improved algorithms for optimal k sink location on path networks

  • Binay Bhattacharya
  • Mordecai J. Golin
  • Yuya Higashikawa
  • Tsunehiko Kameda
  • Naoki Katoh

We address the problem of placing k sinks on dynamic-flow path networks with n vertices so as to minimize their maximum evacuation completion time. We develop two different algorithms that, when all edges have the same capacity, run respectively in O ( n + k 2 log 2 ⁡ n ) and O ( n log ⁡ n ) time. When the edge capacities can be different, i. e. , are general, they run respectively in O ( n log ⁡ n + k 2 log 4 ⁡ n ) and O ( n log 3 ⁡ n ) time. These algorithms improve upon the previously most efficient algorithms, which had time complexities O ( k n ) and O ( k n log 2 ⁡ n ), respectively, for the uniform and general edge capacity models. The improvements are achieved by moving from a dynamic programming based approach to a parametric-search based one.

Details DOI

TCS Journal 2021 Journal Article

Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

  • Yuya Higashikawa
  • Naoki Katoh
  • Junichi Teruyama
  • Koji Watase

We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i. e. , the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm.

Details DOI

TCS Journal 2020 Journal Article

Minsum k-sink problem on path networks

  • Robert Benkoczi
  • Binay Bhattacharya
  • Yuya Higashikawa
  • Tsunehiko Kameda
  • Naoki Katoh

We consider the problem of locating a set of k sinks on a path network with general edge capacities that minimizes the sum of the evacuation times of all evacuees. We first present an O ( k n log 4 ⁡ n ) time algorithm when the edge capacities are non-uniform, where n is the number of vertices. We then present an O ( k n log 3 ⁡ n ) time algorithm when the edge capacities are uniform. We also present an O ( n log ⁡ n ) time algorithm for the special case where k = 1 and the edge capacities are non-uniform.

Details DOI

TCS Journal 2015 Journal Article

Minimax regret 1-sink location problem in dynamic path networks

  • Yuya Higashikawa
  • John Augustine
  • Siu-Wing Cheng
  • Mordecai J. Golin
  • Naoki Katoh
  • Guanqun Ni
  • Bing Su
  • Yinfeng Xu

This paper considers the minimax regret 1-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and each vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location is defined as the minimum time to complete the evacuation for all supplies (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We propose an O ( n log ⁡ n ) time algorithm for the minimax regret 1-sink location problem in dynamic path networks with uniform capacity, where n is the number of vertices in the network.

Details DOI

TCS Journal 2015 Journal Article

Multiple sink location problems in dynamic path networks

  • Yuya Higashikawa
  • Mordecai J. Golin
  • Naoki Katoh

This paper considers the k-sink location problem in dynamic path networks. A dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. A path can be considered as a road, edge lengths as the distance along a road segment and vertex supplies as the number of people at a location. The edges all have a fixed common capacity, which limits the number of people that can enter that edge in a unit of time. The problem is to find the optimal location of k sinks (exits) on the path such that each evacuee is sent to one of the k sinks. The existence of capacities causes congestion, which can slow evacuation down in unexpected ways. Let x be a vector denoting the location of the k sinks. The optimal evacuation policy for x is ( k − 1 ) -dimensional vector d, called ( k − 1 ) -divider. Each component of d corresponds to a boundary dividing all evacuees between adjacent two sinks into two groups, i. e. , all supplies to the right of the boundary evacuate to the right sink and all the others to the left sink. In this paper, we consider optimality defined by two different criteria, the minimax criterion and the minisum one. We prove that the minimax problem can be solved in O ( k n ) time and the minisum problem in O ( n 2 ⋅ min ⁡ { k log ⁡ n + log ⁡ n, 2 log ⁡ k log ⁡ log ⁡ n } ) time, where n is the number of vertices in the given network.

Details DOI

TCS Journal 2015 Journal Article

Optimally bracing grid frameworks with holes

  • Yoshihiko Ito
  • Yuki Kobayashi
  • Yuya Higashikawa
  • Naoki Katoh
  • Sheung-Hung Poon
  • Maria Saumell

We consider the bracing problem of a square grid framework possibly with holes and present an efficient algorithm for making the framework infinitesimally rigid by augmenting it with the minimum number of diagonal braces. This number of braces matches the lower bound given by Gáspár, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1].

Details DOI

TCS Journal 2014 Journal Article

An inductive construction of minimally rigid body–hinge simple graphs

  • Yuki Kobayashi
  • Yuya Higashikawa
  • Naoki Katoh
  • Naoyuki Kamiyama

A d-dimensional body–hinge framework is a collection of d-dimensional rigid bodies connected by hinges, where a hinge is a ( d − 2 ) -dimensional affine subspace, i. e. , pin-joints in 2-space, line-hinges in 3-space, plane-hinges in 4-space and etc. Bodies are allowed to move continuously in R d so that the relative motion of any two bodies connected by a hinge is a rotation around it and the framework is called rigid if every motion provides a framework isometric to the original one. A body–hinge framework is expressed as a pair ( G, p ) of a multigraph G = ( V, E ) and a mapping p from e ∈ E to a ( d − 2 ) -dimensional affine subspace p ( e ) in R d. Namely, v ∈ V corresponds to a body and u v ∈ E corresponds to a hinge p ( u v ) which joins the two bodies corresponding to u and v. Then, G is said to be realized as a body–hinge framework ( G, p ) in R d, and is called a body–hinge graph. It is known [9, 12] that the infinitesimal rigidity of a generic body–hinge framework ( G, p ) is determined only by its underlying graph G. So, a graph G is called (minimally) rigid if G can be realized as a (minimally) infinitesimally rigid body–hinge framework in d-dimension. In this paper, we shall present an inductive construction for minimally rigid body–hinge simple graphs in d-dimension with d ≥ 3.

Details DOI

TCS Journal 2013 Journal Article

A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system

  • Peter Eades
  • Seok-Hee Hong
  • Naoki Katoh
  • Giuseppe Liotta
  • Pascal Schweitzer
  • Yusuke Suzuki

A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition of any edge destroys 1-planarity of G. We first study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected. Using the properties, we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system Φ (i. e. , the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding ξ of G that is consistent with the given rotation system Φ. Our algorithm also produces such an embedding in linear time, if it exists.

Details DOI

TCS Journal 2007 Journal Article

Triangulating a convex polygon with fewer number of non-standard bars

  • Yinfeng Xu
  • Wenqiang Dai
  • Naoki Katoh
  • Makoto Ohsaki

For a given convex polygon with inner angle no less than 2 3 π and boundary edge bounded by [ l, α l ] for 1 ≤ α ≤ 1. 4, where l is a given standard bar’s length, we investigate the problem of triangulating the polygon using some Steiner points such that (i) the length of each edge in triangulation is bounded by [ β l, 2 l ], where β is a given constant and meets 0 < β ≤ 1 2, and (ii) the number of non-standard bars in the triangulation is minimum. This problem is motivated by practical applications and has not been studied previously. In this paper, we present a heuristic to solve the above problem, which is based on the heuristic to generate a triangular mesh with less number of non-standard bars and shorter maximal edge length, and a process to make the length of each edge lower bounded. Our procedure is simple and easily implemented for this problem, and we prove that it has good performance guaranteed.

Details DOI

FOCS Conference 1999 Conference Paper

Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications

  • Naoki Katoh
  • Takeshi Tokuyama

We show that for any line l in space, there are at most k(k+1) tangent planes through l to the k-level of an arrangement of concave surfaces. This is a generalization of L. Lovasz's (1971) lemma, which is a key constituent in the analysis of the complexity of k-level of planes. Our proof is constructive, and finds a family of concave surfaces covering the "laminated at-most-k level". As consequences, (1): we have an O((n-k)/sup 2/3/n/sup 2/) upper bound for the complexity of the k-level of n triangle of space, and (2): we can extend the k-set result in space to the k-set of a system of subsets of n points.

Details

FOCS Conference 1992 Conference Paper

On Minimum and Maximum Spanning Trees of Linearly Moving Points

  • Naoki Katoh
  • Takeshi Tokuyama
  • Kazuo Iwano

The authors investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Suppose that one is given a set of n points in general d-dimensional space, S=(p/sub 1/, p/sub 2/, .. ., p/sub n/), and that all points move along different straight lines at different but fixed speeds, i. e. , the position of p/sub i/ is a linear function of a real parameter. They investigate the numbers of transitions of MinST and MaxST when t increases from - infinity to + infinity. They assume that the dimension d is a fixed constant. Since there are O(n/sup 2/) distances among n points, there are naively O(n/sup 4/) transitions of MinST and MaxST. They improve these trivial upper bounds for L/sub 1/ and L/sub infinity / distance metrics. Let c/sub p/(n, min) (resp. c/sub p/(n, max)) be the number of maximum possible transitions of MinST (resp. MaxST) in L/sub p/ metric for n linearly moving points. They give the following results; c/sub 1/(n, min)=O(n/sup 5/2/a(n)), c/sub infinity /(n, min)=O(n/sup 5/2/a(n)), c/sub 1/(n, max)=O(n/sup n/) and c/sub infinity /(n, max)=O(n/sup 2/) where O(n) is the inverse Ackermann function. They also investigate two restricted cases. >

Details