Naoki Katoh

自由な回転を許すjointおよび伸び縮みのしない堅いbarで構成されるbar and joint frameworkは,jointを頂点集合V, barを辺集合EとするグラフG=(V,E)として扱うことで,組合せ剛性理論の分野ではその剛性について組合せ的特徴付けが為されてきた.特にLamanは2次元上での極小なrigidグラフ(Lamanグラフ)G=(V,E)が満たすべき必要十分条件が|E|=2|V|-3かつ,2点以上からなる任意の部分頂点集合X⊆Vに対して|E(X)|≤2|X|-3であることを示した.一般にrigidグラフは全頂点を使ったLamanグラフを部分グラフとして持つグラフを指す.頂点数2の辺に対してHenneberg I, Henneberg IIと呼ばれる2つの操作を繰り返し行うことで全てのLamanグラフが生成されることが知られている.一方でk-edge-rigidグラフとは, rigidでなくならせるには少なくともk本以上の辺を削除する必要があるような,冗長性を有するrigidグラフであると定義する.Lamanグラフは極小なrigidグラフであることから,極小な1-edge-rigidグラフであると言える.極小な2-edge-rigidグラフはcircuitグラフとして知られているが,k≥3に関してはその構造については知られていない.本研究ではLamanグラフを2-edge-rigidグラフへと冗長化させる問題および辺数最小の3-edge-rigidグラフの生成手法について述べる.

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.

A d-dimensional body-and-hinge framework is, roughly speaking, a structure consisting of rigid bodies connected by hinges in d-dimensional space. The generic infinitesimal rigidity of a body-and-hinge framework has been characterized in terms of the underlying multigraph independently by Tay and Whiteley as follows: A multigraph G can be realized as an infinitesimally rigid body-and-hinge framework by mapping each vertex to a body and each edge to a hinge if and only if ((d+1 2)-1) G contains (d+2 1) edge-disjoint spanning trees, where ((d+1 2)-1) G is the graph obtained from G by replacing each edge by ((d+1 2)-1) parallel edges. In 1984 they jointly posed a question about whether their combinatorial characterization can be further applied to a nongeneric case. Specifically, they conjectured that G can be realized as an infinitesimally rigid body-and-hinge framework if and only if G can be realized as that with the additional "hinge-coplanar" property, i.e., all the hinges incident to each body are contained in a common hyperplane. This conjecture is called the Molecular Conjecture due to the equivalence between the infinitesimal rigidity of "hinge-coplanar" body-and-hinge frameworks and that of bar-and-joint frameworks derived from molecules in 3-dimension. In 2-dimensional case this conjecture has been proved by Jackson and Jordan in 2006. In this paper we prove this long standing conjecture affirmatively for general dimension. Also, as a corollary, we obtain a combinatorial characterization of the 3-dimensional bar-and-joint rigidity matroid of the square of a graph.

In this paper, we consider the following covering problem in graphs which is motivated by patrol route planning. Suppose that we are given a graph G=(V,E), a cost function c:2^E→R_+ and a requirement function r:V→Z_+, where R_+ and Z_+ represent the set of nonnegative reals and integers, respectively. Then, we consider the problem of finding minimum cost k subgraphs with a prescribed property (e.g., trees or paths) such that each v∈V is contained in at least r(v) subgraphs, where the cost of each subgraph is defined by the value of the function c for its edge set and the cost of k subgraphs is defined by the sum of their costs. Since this problem includes the travelling salesman problem as a subcase, it is NP-hard. In this paper, we consider two special cases of this problem. We first consider the problem where we cover the input graph by using trees. For this problem, we present a heuristic algorithm and we apply our algorithm to a numerical example arising from Nagoya City in Japan. We next consider the problem where we are given a path as the input graph and we cover it by using subpaths. For this problem, we first show that if each edge is given a cost and the cost of each path is defined by the sum of the costs of the edges contained in it, this problem can be solved in time bounded by a polynomial in the size of G, k and max{r(v)|v∈V}. Next, we show that if k=max{r(v)|v∈V}holds, this problem can be solved in polynomial time for a general cost function. Furthermore, we prove that if each edge is given a cost and the cost of each path is defined by the square of the sum of the costs of the edges contained in it, we can solve this problem more efficiently.

Given a directed graph D=(V,A) and a set of specified vertices S={s_1,…s_d}⊆V with |S|=d and a function f: S→N where N denotes the set of natural numbers, we present a necessary and sufficient condition that there exist Σ_<s_i∈S>f(s_i) arc-disjoint in-trees denoted by T_<i,1>, T_<i,2>,…,T_<i,f(s_i)> for every i=1,…,d such that T_<i,1>,…,T_<i,f(s_i)> are rooted at s_i and each T_<i,j> spans vertices from which s_i is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s∈V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.

In this paper we present an algorithm for enumerating without repetitions all non-crossing geometric spanning trees on a given set of n points in the plane including a given necessary edge set. Our enumeration algorithm generates each output graph in O(n^2) time and O(n) space based on reverse search technique. This result improves the previous O(n^3) bound for the unconstrained case by factor of O(n). Our algorithm deal with the edge-constrained case in the same running time.

In this paper, we consider the following covering problem arising from evacuation planning problems. Given a directed graph D=(V, A) with a set of d specified vertices S={s_1,...,s_d}⊆V and a function f:S→Z_+ where Z_+ denotes the set of non-negative integers, our problem asks whether there exist a set of Σ^d_<i=1>f(si) in-trees {T_<i,j>: i=1,...,d,j=1,...,f(s_i)} such that each T_<i,j> is rooted at s_i and spans vertices from which s_i is reachable, and the union of all arc sets of T_<i,j> for i=1,...,d and j=1,...,f(s_i) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in Σ^d_<i=1>f(si) and the size of D. Moreover, we prove that if D is acyclic, we can solve this problem more efficiently that general case by finding maximum matchings in a series of bipartite graphs instead of using an algorithm for the weighted matroid intersection problem.

An efficient approach for generating pin-jointed compliant mechanisms is presented. A compliant mechanism uses the elastic deformation of structural parts to realize the mechanism for shape transformation of the entire structure, which is contrary to the conventional link mechanism. Ohsaki and Nishiwaki (Struct. Multidisc. Optim., Vol.30, pp.327-334, 2005) presented a method for generating flexible multistable bar-joint mechanisms using nonlinear programming approach. However, due to highly nonlinear property of the problem, the nonlinear programming problem should be solved many times with random initial solutions to obtain several types of mechanisms. Since the compliant pin-jointed mechanism is usually statically determinate, the optimization problem can be solved easily if the design space is limited to statically determinate structures. Avis et al. (Proc. of COCOON 2006, LNCS 4112, pp.205-215, 2006) presented an algorithm for enumerating all the non-crossing generically minimally rigid bar-joint frameworks, which are regarded as statically determinate trusses in structural engineering. In this paper, bistable mechanisms utilizing snapthrough behavior are obtained more efficiently with the algorithm. In the numerical example, many types of bistable compliant mechanisms are generated.

In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks (also called non-crossing Laman frameworks) on a given generic set of n points. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n^4) time and O(n) space, or, with a slightly different implementation, in O(n^3) time and O(n^2) space. In particular, we obtain that the set of all non-crossing Laman frameworks on a given point set is connected by flips which remove an edge and then restore the minimally rigid property with the addition of a non-crossing edge.

In this paper we present and algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraint (also called constrained non-crossing Laman frameworks) on a given generic set of n points. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n^3) time and O(n^2) space.