加藤 直樹

We consider an online traveling salesman problem in a simple polygon where starting from a point in the interior of a simple polygon, the searcher is required to explore a simple polygon to visit its all vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.We consider an online traveling salesman problem in a simple polygon where starting from a point in the interior of a simple polygon, the searcher is required to explore a simple polygon to visit its all vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm.

自由な回転を許す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グラフの生成手法について述べる.

本研究では複数人の探索者によるオンライングラフ探索問題を扱う.探索の目的は,すべての頂点が少なくとも1人の探索者によって到達されることである.すべての探索者は同一の頂点を探索の始点とし,同一の移動速度で探索を行う.また,すべての探索者は他の探索者が新しく入手した情報を常に共有することが出来る.本稿では特にグラフクラスをサイクル,木とする問題に対するアルゴリズムをそれぞれ与え,競合比解析を行う.具体的には探索者数を2とするサイクルの探索に対して最適な競合比3/2を達成するアルゴリズムを与え,さらに探索者数をpとする木の探索に対して最適な競合比(p/(log p))+o(1)を達成するアルゴリズムを与える.

d次元空間上の剛体ヒンジ構造とはd次元の部分空間(剛体)が(d-2)次元アフィン空間(ヒンジ)によって接続された構造物であり，各剛体は接続されたヒンジ周りを回転し動く事が出来る．特に各剛体が(d-1)次元アフィン空間(剛板)として実現される際，構造物は剛板ヒンジ構造と呼ばれる．剛体ヒンジ構造物の1次剛性は，その接続関係の組合せ構造によって特徴付けされる事が知られており，1984年にTay and Whiteleyはその組合せ的特徴付けが剛板ヒンジ構造物に対しても適用可能であると予想した．より正確には「グラフGに対して，各頂点を剛板，各辺をヒンジに対応させ実現される剛板ヒンジ構造が全体として剛となる必要十分条件は((d+1/2)-1)Gが(d+1/2)個の辺素な全域木を含む事である」という予想を彼らは行った．ここで((d+1/2)-1)GはGの各辺を((d+1/2)-1)個の多重辺で置き換えたグラフである．3次元空間において分子構造の1次剛性は剛板ヒンジ構造物を用いて表現できる事が知られており，そのためこの予想は"the Molecular Conjecture"と呼ばれている．本稿では，長年未解決であったこの予想に対する証明を与える．またこの結果から，G2の辺集合を台集合とする3次元剛性マトロイドの組合せ的特徴付けが得られる．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+1/2) 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.

本論文では，｜S|＝ｄを満たす特別な点集合S＝{S1 ... Sd.｝⊆Ｖを持つ有向グラフD＝(V A) と関数 f:S→Nが与えられたとき，各 Ti ｊ が ｓｉ を根とし，ｓｉ に到達可能なVの点集合を張るような，全てのi＝1 ... dに対して、Ti 1 Ti 2... Ti ｆ(si）と表される辺素な内向木の集合が存在する必要十分条件を与える．ただし，Nは自然数の集合であるとする．この定理は，［2]によって与えられた定理，つまり特別な点S∈Vを持つ有向木D＝(V A)と自然数K∈Nが与えられたとき，虎個の辺素なVを張るsを根とする内向木が存在する必要十分条件の一般化となっている．さらに本論文では，［1]によって与えられた内向木のパッキングに関する別の特徴付けを，我々の場合へ拡張する．Given a directed graph D = (V,A) and a set of specified vertices S = {s1..., sd} ⊆ 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 Σsi∈s f(si) arc-disjoint in-trees denoted by Ti,1,Ti,2,....,Ti,f(si) for every i = 1,..., d such that Ti,1,..., Ti,f(si) are rooted at Si and each Ti,j spans vertices from which si 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.

平面上の$n$点からなる点集合$P$と$P$上の無交差な辺の集合$F$が与えられた際，$P$上の$F$を部分集合として含む全域木を$F$制約付き全域木と呼ぶ．本論で提案するアルゴリズムは$P$上の$F$制約付き無交差全域木を一つ当たり$O(n^2)$の計算時間で列挙を行う.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.

本論文では，d 個の特別な点の集合 S = {s1 ... sd} ⊆ V を持つ有向グラフ D = (V A) と関数 ?: S→Z+ ( Z+ は非負整数の集合）が与えられたとき，各Τi j がsi を根とし， si に到達可能な点集合を張り，そして全ての i = 1 … d に対するTi 1 … Ti f (si) の辺集合の合併が A を被覆するような，∑= 1 ? (si) 個の内向木の集合 {T i j : i = 1 …d j = 1 … ? (s_i) } の存在を判定する問題を考える．本論文では，この問題が重みつきマトロイド交差アルゴリズムを用いることにより， D のサイズと ∑= 1 ? (si) の多項式時間で解けることを示す．さらに，D が閉路を持たない場合は，重みつきマトロイド交差アルゴリズムの代わりに，二部グラフの最大マッチングアルゴリズムを用いることで，高速に解くことができることを示す．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 = {s1,…,sd} ⊆ V and a function ﾆ驤: S→Z+ where Z+ denotes the set of non-negative integers, our problem asks whether there exist a set of Σ=1ﾆ驤 (si) in-trees {Ti,,j :i = 1,…, d, j = 1,,…, ﾆ驤 (si) } such that each Ti,j is rooted at si and spans vertices from which si is reachable, and the union of all arc sets of Ti,j for i = 1,…, d and j = 1,…, ﾆ驤 (si) 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 Σ=1 ﾆ驤 (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.

本論では,平面上に一般の位置に与えられたn頂点からなる頂点集合Pに対して,P上に埋め込まれた,辺制約付き非交差静定グラフをすべて列挙するアルゴリズムについて述べる.静定グラフはラーマングラフとも呼ばれ,そのようなグラフ全体がマトロイドの基を作ることが知られている.一方,平面上に埋め込まれた無交差ラーマングラフ全体はマトロイドとはならない.本論文では,Avis and Fukudaによる逆探索法を用いて,無交差ラーマングラフの列挙が可能であることを示す.またあらかじめ用いる辺が一部指定されている場合も列挙が可能である.