Yuya Higashikawa

Evacuation in emergency situations can be modeled by a dynamic flow network.<br /> Two criteria have been used before: one is the evacuation completion time and<br /> the other is the aggregate evacuation time of individual evacuees. The aim of<br /> this paper is to optimize the aggregate evacuation time in the simplest case,<br /> where the network is a path and only one evacuation center (called a sink) is<br /> to be introduced. The evacuees are initially located at the vertices, but their<br /> precise numbers are unknown, and are given by upper and lower bounds. Under<br /> this assumption, we compute the sink location that minimizes the maximum<br /> &quot;regret.&quot; We present an $O(n^2\log n)$ time algorithm to solve this problem,<br /> improving upon the previously fastest $O(n^3)$ time algorithm, where $n$ is the<br /> number of vertices.

A Dynamic Graph Network is a graph in which each edge has an associated<br /> travel time and a capacity (width) that limits the number of items that can<br /> travel in parallel along that edge. Each vertex in this dynamic graph network<br /> begins with the number of items that must be evacuated into designated sink<br /> vertices. A $k$-sink evacuation protocol finds the location of $k$ sinks and<br /> associated evacuation movement protocol that allows evacuating all the items to<br /> a sink in minimum time. The associated evacuation movement must impose a<br /> confluent flow, i.e, all items passing through a particular vertex exit that<br /> vertex using the same edge. In this paper we address the $k$-sink evacuation<br /> problem on a dynamic path network. We provide solutions that run in $O(n \log<br /> n)$ time for $k=1$ and $O(k n \log^2 n)$ for $k &gt;1$ and work for arbitrary edge<br /> capacities.

We first consider the weighted p-center problem, in which the centers are constrained to lie on two axis-parallel lines. Given a set of n points in the plane, which are sorted according to their x-coordinates, we show how to test in O(n log n) time if p piercing points placed on two lines, parallel to the x-axis, can pierce all the disks of different radii centered at the n given points. This leads to an O(n log(2) n) time algorithm for the weighted p-center problem. We then consider the unweighted case, where the centers are constrained to be on two perpendicular lines. Our algorithm runs in O(n log(2) n) time in this case as well.

A dynamic network ${\cal N} = (G,c,\tau,S)$ where $G=(V,E)$ is a graph,<br /> integers $\tau(e)$ and $c(e)$ represent, for each edge $e\in E$, the time<br /> required to traverse edge $e$ and its nonnegative capacity, and the set<br /> $S\subseteq V$ is a set of sources. In the $k$-{\sc Sink Location} problem, one<br /> is given as input a dynamic network ${\cal N}$ where every source $u\in S$ is<br /> given a nonnegative supply value $\sigma(u)$. The task is then to find a set of<br /> sinks $X = \{x_1,\ldots,x_k\}$ in $G$ that minimizes the routing time of all<br /> supply to $X$. Note that, in the case where $G$ is an undirected graph, the<br /> optimal position of the sinks in $X$ needs not be at vertices, and can be<br /> located along edges. Hoppe and Tardos showed that, given an instance of<br /> $k$-{\sc Sink Location} and a set of $k$ vertices $X\subseteq V$, one can find<br /> an optimal routing scheme of all the supply in $G$ to $X$ in polynomial time,<br /> in the case where graph $G$ is directed. Note that when $G$ is directed, this<br /> suffices to obtain polynomial-time solvability of the $k$-{\sc Sink Location}<br /> problem, since any optimal position will be located at vertices of $G$.<br /> However, the computational complexity of the $k$-{\sc Sink Location} problem on<br /> general undirected graphs is still open. In this paper, we show that the<br /> $k$-{\sc Sink Location} problem admits a fully polynomial-time approximation<br /> scheme (FPTAS) for every fixed $k$, and that the problem is $W[1]$-hard when<br /> parameterized by $k$.

We study three-dimensional bar-joint frameworks of the space-filling structure. A truss structure is a kind of bar-joint framework, which is a structure composed of rigid rods (bars) connected at their ends (free joints). Here, a space-filling convex polyhedron is a convex polyhedron which can be used to generate a tessellation of space. Such frameworks are known to be flexible, but we present an efficient algorithm for making the frameworks infinitesimally rigid by augmenting it with adding minimum number of diagonal braces.

In this paper, we prove that frameworks of convex polyhedra remain infinitesimally rigid even if we remove a set of edges which do not share their end points (matching edges). We also present a sufficient condition that the frameworks remain infinitesimally rigid even if we remove their panels which do not share their vertices. We study these two problems assuming that hinges of the frameworks are in a generic position, in other words all the vectors of hinges are algebraically independent of each other.

本研究では、直交する 3 種類の長方形パネルに限定した剛な panel-hinge フレームワークを実現する問題を考察する。Higashikawa らは最近、極小剛な panel-hinge graph をすべて導出するアルゴリズムを提案しているが、われわれが考察するフレームワークは generic ではないので、このアルゴリズムは適用できない。そこで、panel-hinge framework を導出する新たな操作を捉案し、それにもとづき、直交するパネルによるフレームワーク生成法を構築する。

This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Here, each vertex supply corresponds to a set of evacuees. Then, the problem requires to find the optimal location of k sinks in a given path so that each evacuee is sent to one of k sinks. Let x denote a k-sink location. Under the optimal evacuation for a given x, there exists a (k-1)-dimensional vector d, called (k-1)-divider, such that each component represents the boundary dividing all evacuees between adjacent two sinks into two groups, i.e., all supplies in one group evacuate to the left sink and all supplies in the other group evacuate to the right sink. Therefore, the goal is to find x and d which minimize the maximum cost or the total cost, which are denoted by the minimax problem and the minisum problem, respectively. We study the k-sink location problem in dynamic path networks with continuous model, and prove that the minimax problem can be solved in O(kn log n) time and the minisum problem can be solved in O(kn(2)) time, where n is the number of vertices in the given network.

In this paper, we prove that a body-hinge graph G is (k-1)-edge-rigid if and only if G is k-edge-connected (k≧3). A body-hinge graph G is k-edge-rigid if removing any (k-1) edges from G results in a graph which is rigid. Furthermore, we prove that a body-hinge graph G is k-vertex-connected if G is k-vertex-rigid and that a body-hinge graph G is (k-h,h+2)-rigid with h (0≦h≦k-1) if G is (k+2)-vertex-connected (k≧1). A body-hinge graph G is k-vertex-rigid if removing any (k-1) vertices from G results in a graph which is rigid. A body-hinge graph G is (i,j)-rigid if removing any (i-1) vertices from G results in a graph which is j-edge-rigid.

This paper considers the k-sink location problem in dynamic path networks. In our model, a dynamic path network consists of an undirected path with positive edge lengths, uniform edge capacity, and positive vertex supplies. Let x denote a k-sink location. Under the optimal evacuation to a given x, any two evacuation paths never cross each other. Additionally, we assume that all evacuees given at the same vertex evacuate to the same sink. Then, there exists a (k-1)-vector d, called (k-1)-divider, such that each component represents the boundary dividing all evacuees between adjacent two sinks into two groups, i.e., one group evacuates to the left sink and the other group evacuates to the right sink. Then, the problem is to find x and d which minimizes the time required for all evacuees on a path divided by d to complete evacuation to x. We present an O(kn log n) time algorithm for the k-sink location problem in a dynamic path network with uniform capacity, where n is the number of vertices in the given network.

This paper considers minimax regret 1-sink location problems 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 the 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 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 present an O(n log n) time algorithm for minimax regret 1-sink location problems in dynamic path networks with uniform capacity, where n is the number of vertices in the network. This improves upon the existing time bound of O(n log^2 n) by [6].

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている．3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが，その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている．剛体(body)を頂点，剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ．本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する．まず，所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し，この操作によりすべてのbody-hingeグラフが生成可能であることを証明する．これにより，すべてのbody-hingeグラフを生成するアルゴリズムを提案する．計算時間は一つのbody-hingeグラフあたり多項式時間で済む．

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている.3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが,その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている.剛体(body)を頂点,剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ.本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する.まず,所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し,この操作によりすべてのbody-hingeグラフが生成可能であることを証明する.これにより,すべてのbody-hingeグラフを生成するアルゴリズムを提案する.計算時間は一つのbody-hingeグラフあたり多項式時間で済む.

This paper deals with online graph exploration problems by muitiple searchers. The purpose of search is to visit all vertices by at least one searcher. It is assumed that searchers stay at the origin at the beginning and start to explore a graph with the same speed, and that they can communicate with each other to share the whole information gathered by at least one searcher. We consider two cases of graphs, cycles and trees. For cycles, we establish an optimal algorithm of 3/2-competitive ratio with two searchers. For trees, we establish an optimal algorithm with P searchers of (p/(log p))+o(1)-competitive ratio.

This paper deals with online graph exploration problems by muitiple searchers. The purpose of search is to visit all vertices by at least one searcher. It is assumed that searchers stay at the origin at the beginning and start to explore a graph with the same speed, and that they can communicate with each other to share the whole information gathered by at least one searcher. We consider two cases of graphs, cycles and trees. For cycles, we establish an optimal algorithm of 3/2-competitive ratio with two searchers. For trees, we establish an optimal algorithm with P searchers of (p/(log p))+o(1)-competitive ratio.