加藤 直樹

This paper presents novel algorithms for enumerating architectural floor plans. The enumeration approach attempts to generate all feasible solutions that satisfy given constraints. Therefore, such a method might usefully reveal the potential diversity of Open Building floor plans. However, combinatorial enumeration solutions easily explode even for small problem sizes. We represent a space by a set of cells and organize some cells into polyomino-like configurations. We then enumerate all cell combinations that can be tiled in the given space using an efficient search algorithm for combinatorial problems. We also propose queries for extracting specific floor plans that satisfy additional constraints from all enumerated floor plans without re-enumeration. Our approach solves a 56-cell configuration space within a realistic timeframe.

A panel-hinge framework is a structure composed of rigid panels connected by hinges. It was recently proved that at a generic position, the rigidity of panel-hinge frameworks can be predicted by examining a certain combinatorial property of the underlying graph. In this study, we apply such combinatorial characteristics to create design forms. When considering the application of design forms, we must also take into account non-generic cases. In this paper we develop two new approaches the first one that the method inductively generates non-generic rigid panel-hinge frameworks consisting of orthogonal panels and the second one that inductively generates non-generic rigid panel-hinge frameworks based on fractal geometry coupled with space-filling convex polyhedron as a construction unit. We will give examples of forms created by the proposed method in order to demonstrate the applicability of the proposed methods to design forms.

最速避難計画問題は,動的ネットワークの頂点上に存在するすべての避難者ができるだけ早く避難所のいずれかに移動する計画を求める問題である.本稿では,この問題を高速に解くヒューリスティックスを紹介する.具体的に大阪市湾岸地域における津波からの最速避難計画に適用した例を紹介する.

We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing.

In the universally quickest transshipment problem, we are given a network with a transit time function on its arc set. The goal is to minimize the time when the last supply reaches the sink and to maximize the amount of supplies which have reached the sink at every time step. In this paper, we consider this problem in a class of dynamic networks which is a generalization of grid networks with uniform capacity and uniform transit time, and present a polynomial-time algorithm for this case. (C) 2014 Elsevier B.V. All rights reserved.

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 is an element of E to a (d - 2)-dimensional affine subspace p(e) in R-d. Namely, v is an element of V corresponds to a body and uv is an element of E corresponds to a hinge p(uv) 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. (C) 2014 Elsevier B.V. All rights reserved.

This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model among searchers, searchers can share the information about the environment. Thus, a searcher must decide which vertex to visit next based on the partial information on the graph gained so far by searchers. We assume that all searchers initially start the exploration at the origin vertex, and the goal is that each vertex is visited by at least one searcher and all searchers finally return to the origin vertex. The objective is to minimize the time when the goal is achieved. We study the case of cycles and trees. For the former, we give an optimal online exploration algorithm in terms of competitive ratio, and for the latter, we also give an online exploration algorithm which is optimal among greedy algorithms.

This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model among searchers, searchers can share the information about the environment. Thus, a searcher must decide which vertex to visit next based on the partial information on the graph gained so far by searchers. We assume that all searchers initially start the exploration at the origin vertex, and the goal is that each vertex is visited by at least one searcher and all searchers finally return to the origin vertex. The objective is to minimize the time when the goal is achieved. We study the case of cycles and trees. For the former, we give an optimal online exploration algorithm in terms of competitive ratio, and for the latter, we also give an online exploration algorithm which is optimal among greedy algorithms.

This paper addresses the minimax regret sink location problem in dy- namic tree networks. In our model, a dynamic tree network consists of an undirected tree with positive edge lengths and uniform edge capacity, and the vertex supply which is a positive value is unknown but only the interval of supply is known. A particular realization of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location x is defined as the minimum time to complete the evacuation to x for all supplies (evacuees), and the regret of x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a sink location which minimizes the maximum regret for all possible scenarios. We present an O(n2 log2 n) time algorithm for the minimax regret sink location problem in dynamic tree networks with uniform capacity, where n is the number of vertices in the network. As a preliminary step for this result, we also address the minimum cost sink location problem in a dy- namic tree networks under a fixed scenario and present an O(n log n) time algorithm, which improves upon the existing time bound of O(n log2 n) by [14] if edges of a tree have uniform capacity.

Open Building (Habraken, 1972) has been the focus of attention due to growing interest in the sustainable society. For Open Building, it is important to preserve the diversity of feasible floor plans in order to adapt to various lifestyles of residents. Capacity analysis is a method for evaluating the potential diversity. We propose a novel method that evaluates the potential diversity of floor plans by enumerating all feasible floor plans satisfying given constraints based on zero-suppressed binary decision diagram (ZDD) (Minato, 1993).

A panel-hinge framework is a structure composed of rigid panels connected by hinges. It was recently proved that for a so-called generic position, the rigidity of panel-hinge frameworks can be tested by examining the combinatorial property of the underlying graph. In this study, we apply such combinatorial characteristics to create design forms. However, such characterization is only valid for so-called "generic" panel-hinge frameworks. When considering the application of design forms, we need to take into account non-generic cases. In this paper, we develop the method to inductively generate non-generic rigid panel-hinge frameworks consisting of orthogonal panels and to inductively generate rigid panel-hinge frameworks based on fractal geometry coupled with space filling 3-dimensional convex polyhedron as a construction unit. We give examples of forms by the proposed method to demonstrate the applicability to design forms.

This paper addresses the minimax regret sink location problem in dynamic tree networks. In our model, a dynamic tree network consists of an undirected tree 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 realization of supply to each vertex is called a scenario. Under any scenario, the cost of a sink location x is defined as the minimum time to complete the evacuation to x for all supplies (evacuees), and the regret of x is defined as the cost of x minus the cost of the optimal sink location. Then, the problem is to find a sink location minimizing the maximum regret for all possible scenarios. We present an O(n(2) log(2) n) time algorithm for the minimax regret sink location problem in dynamic tree networks with uniform capacity, where n is the number of vertices in the network. As a preliminary step for this result, we also address the minimum cost sink location problem in a dynamic tree networks under a fixed scenario and present an O(n log n) time algorithm, which improves upon the existing time bound of O(n log(2) n) by [11] if edges of a tree have uniform capacity.

Recently, Cheng et al. [1] proposed the minimax regret 1-sink location problem in dynamic path networks and presented an O(n log(2) n) time algorithm for the proposed problem, where n is the number of vertices. In this paper, we study the general problem, i.e., minimax regret k-sink location problem in the dynamic path networks. Based on the algorithm for the 1-sink location problem, we design an O(n(2) (log n)(1+log k) C-n(k-1)) time algorithm for the general problem, where C-n(k-1) is the number of combination choosing k - 1 from n.

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 Gaspar, Radics and Recski [2]. Our contribution extends the famous result on bracing the rectangular grid framework by Bolker and Crapo [1].

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.

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 Phi (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 xi of G that is consistent with the given rotation system Phi. Our algorithm also produces such an embedding in linear time, if it exists. (C) 2013 Elsevier B.V. All rights reserved.

We analyze the energy consumption data of tenants in office buildings in Tokyo and show that it is able to estimate the specific energy consumption of each tenant with a high degree of accuracy by using a linear mixed model. We obtain the result that attributes which strongly influence on the basic unit are temperature, tenant type and so on. From the observation of random effects, we know that the main factor to the basic unit is the individuality of tenants. We also clarify effective power saving behaviors after the Great East Japan Earthquake by a random effect.

This paper considers online vertex exploration problems in a simple polygon where starting from a point in the inside of a simple polygon, a searcher is required to explore a simple polygon to visit all its 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.

As a vertex-disjoint analogue of Edmonds' arc-disjoint arborescences theorem, it was conjectured that given a directed graph D with a specified vertex r, there are k spanning arborescences rooted at r such that for every vertex v of D the k directed walks from r to v in these arborescences are internally vertex-disjoint if and only if for every vertex v of D there are k internally vertex-disjoint directed walks from r to v. Whitty (1987) [10] affirmatively settled this conjecture for k <= 2, and Huck (1995) [6] constructed counterexamples for k >= 3, and Huck (1999) [7] proved that the conjecture is true for every k when D is acyclic. In this paper, we generalize these results by using the concept of "convexity" which is introduced by Fujishige (2010) [4]. (C) 2012 Elsevier B.V. All rights reserved.

The resource allocation problem seeks to find an optimal allocation of a fixed amount of resources to activities so as to minimize the cost incurred by the allocation. A simplest form of the problem is to minimize a separable convex function under a single constraint concerning the total amount of resource to be allocated. The amount of resource to be allocated to each activity is treated as a continuous or integer variable, depending on the situations. Hence, this problem can be viewed as a special case of the nonlinear programming problem or the nonlinear integer programming problem. Due to its simple structure, the resource allocation problem is encountered in a variety of application areas, including load distribution, production planning, computer resource allocation, queueing control, portfolio selection, and apportionment. The first explicit investigation of the resource allocation problem was due to a paper by Koopman [89] published in 1953, where he discussed optimal distribution of efforts which arises from the problem of searching for an object whose position is a random variable. Since then, a great number of papers on the resource allocation problem have been published. Efficient algorithms have also been developed, depending on the types of objective functions, constraints, and variables (i.e., continuous or integer). In 1988, two of the present authors, Ibaraki and Katoh, have published a book [69] that gave a comprehensive review of the state of the art of the resource allocation problem. Since then, more than 20 years have passed, during which, many papers on this problem have been published. A significant progress has been made on the algorithm side. Also, new generalizations and variants of the problem have been investigated, and new application fields have been discovered. The main purpose of this chapter is to give a brief overview of the recent progress on the theory and applications, putting emphasis on the cases with integer variables.

Japanese cities always have risks of large-scale earthquakes. Thus, it is very important to establish crisis management systems against large-scale disasters such as big earthquakes, and tsunamis to secure evacuation centers for evacuees. In this respect, it is extremely important to provide sufficient evacuation centers and to appropriately partition the whole region into small areas, such that a unique evacuation center is located in each area and the people living in the area can easily evacuate to the center. However, it is hard to find an optimal region partitioning, due to the uncertainty, such as a fire or collapsed buildings. In this research, we propose a method to enumerate all partitioning patterns using Zero-suppressed Binary Decision Diagram (ZDD) that satisfy several conditions. We apply the proposed method to Kamigyo Ward of Kyoto City, Japan. © 2013 IET.

This paper is concerned with the crossing number of Euclidean minimum-weight Laman graphs in the plane. We first investigate the relation between the Euclidean minimum-weight Laman graph and proximity graphs, and then we show that the Euclidean minimum-weight Laman graph is quasi-planar and 6-planar. Thus the crossing number of the Euclidean minimum-weight Laman graph is linear in the number of points.

This paper considers minimax regret 1-sink location problems in dynamic path networks. A dynamic path network consists of an undirected path with positive edge lengths and constant edge capacity and the vertex supply which is nonnegative value, called weight, is unknown but only the interval of weight is known. A particular assignment of weight to each vertex is called a scenario. Under any scenario, the cost of a sink is defined as the minimum time to complete evacuation for all weights (evacuees), and the regret of a sink location x is defined as the cost of x minus the cost of an optimal sink. 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 log2 n) time algorithm for minimax regret 1-sink location problems in dynamic path networks, where n is the number of vertices in the network. © Springer-Verlag Berlin Heidelberg 2013.

In this paper, we propose an inductive construction of minimally rigid body-hinge simple graphs. Inductive construction is one of well-studied topics in Combinatorics and Combinatorial Optimization. We develop an inductive construction for minimally rigid body-hinge simple graphs in d-dimension with d ≥ 3 by which we can develop a polynomial-time algorithm for enumerating all minimally rigid body-hinge simple graphs. © Springer International Publishing 2013.

A graph is 1-planar if it can be embedded in the plane with at most one crossing per edge. A graph is outer-1-planar if it has an embedding in which every vertex is on the outer face and each edge has at most one crossing. We present a linear time algorithm to test whether a graph is outer-1-planar. The algorithm can be used to produce an outer-1-planar embedding in linear time if it exists. © 2013 Springer International Publishing Switzerland.

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. A 1-planar embedding of a graph G is maximal if no edge can be added without violating the 1-planarity of G. In this paper 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 preserves the given rotation system, and our algorithm produces such an embedding in linear time, if it exists. © 2013 Springer-Verlag.

As an extension of a classical tree-partition problem, we consider decompositions of graphs into edge-disjoint (rooted-)trees with an additional matroid constraint. Specifically, suppose that we are given a graph G = (V,E), a multiset R = {r1,.., rt} of vertices in V, and a matroid M on R. We prove a necessary and sufficient condition for G to be decomposed into t edge-disjoint subgraphs G1 = (V1, T1),..,Gt = (Vt, Tt) such that (i) for each i, Gi is a tree with ri ε Vi, and (ii) for each v ε V, the multiset {ri ε R | v ε Vi} is a base of M. If M is a free matroid, this is a decomposition into t edge-disjoint spanning trees thus, our result is a proper extension of Nash-Williams' tree-partition theorem. Such a matroid constraint is motivated by combinatorial rigidity theory. As a direct application of our decomposition theorem, we present characterizations of the infinitesimal rigidity of frameworks with nongeneric "boundary," which extend classical the Laman's theorem for generic 2-rigidity of bar-joint frameworks and Tay's theorem for generic d-rigidity of body-bar frameworks. © 2013 Society for Industrial and Applied Mathematics.

This paper is concerned with the crossing number of Euclidean minimum-weight Laman graphs in the plane. We first investigate the relation between the Euclidean minimum-weight Laman graph and proximity graphs, and then we show that the Euclidean minimum-weight Laman graph is quasi-planar and 6-planar. Thus the crossing number of the Euclidean minimum-weight Laman graph is linear in the number of points.

A rooted-forest is the union of vertex-disjoint rooted-trees. Suppose we are given a graph G=(V,E), a collection {R (1),aEuro broken vertical bar,R (k) } of k root-sets (i.e., vertex-sets), and a positive integer d. We prove a necessary and sufficient condition for G to contain k edge-disjoint rooted-forests F (1),aEuro broken vertical bar,F (k) with root-sets R (1),aEuro broken vertical bar,R (k) such that each vertex is spanned by exactly d of F (1),aEuro broken vertical bar,F (k) .

This paper considers an online exploration 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 all its 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. © 2012 Springer-Verlag.

本論文では,スポーツの勝敗を定める確率モデルとしてよく知られているBradley-Terryモデルを仮定して,スポーツの団体戦における勝敗決定方法として採用されている勝ち抜き戦およびせん滅戦における選手の最適出場順序について考察する.勝ち抜き戦,せん滅戦およびその一般形においてはチームの勝利確率が選手の出場順序に依存しないことを示す.また,点取り方式の団体戦の最適出場順序についても言及する.

The inspection and repair service in office buildings is one of the important tasks for an enterprise which provides property management services, and reducing costs incurred by the services is required for the enterprise. However, the content of the services is obscure and the location of the service center is not often optimized. With the background, we provide quantitative analysis of the service, especially the contents of the service and the working hours, and optimize the location of the service center.

The authors propose a method to estimate the retention of stretch of polyvinyl chloride resin waterproofing sheet using image analysis techniques. The retention of stretch is regarded as the index of deterioration of a waterproofing sheet. Firstly, we originally developed a microscope for taking digital images of the surface of water proofing sheets that can capture the crack clearly. Then various kinds of existing image attributes are adopted to characterize the crack. These features are used as explanatory variables of multiple linearregressions to estimate the retention of the stretch. Estimation models were created and validated through cross validation tests. Finally, we succeeded in creating the estimation model that exhibits about 0.96 in determination coefficient.

We prove the Molecular Conjecture posed by Tay and Whiteley. This implies that a graph G can be realized as an infinitesimally rigid panel-hinge framework in a"e (d) by mapping each vertex to a rigid panel and each edge to a hinge if and only if parallel edges.

In recent years, catastrophic disasters by massive earthquakes are increasing in the world, and disaster management is required more than ever. In the case of disasters such as tsunami from which the slight delay of evacuation deprives of life. In this article, we formalize the emergency evacuation planning model for the evacuation from tsunami etc. based on the idea of the universally quickest flow. We will show that there does not always exist a universally quickest flow when the capacity constraint of refuges is taken into account. Therefore, we will propose an alternative criterion that approximates a universally quickest flow, and presents an algorithm for finding an optimal flow for this criterion. Numerical experiments of the evacuation aimed at a local city in Japan are carried out where tsunami damages are assumed to occur when a big earthquake occurs in the ocean nearby.

In recent years, catastrophic disasters by massive earthquakes are increasing in the world, and disaster management is required more than ever. In the case of disasters such as tsunami from which the slight delay of evacuation deprives of life. In this article, we formalize the emergency evacuation planning model for the evacuation from tsunami etc. based on the idea of the universally quickest flow. We will show that there does not always exist a universally quickest flow when the capacity constraint of refuges is taken into account. Therefore, we will propose an alternative criterion that approximates a universally quickest flow, and presents an algorithm for finding an optimal flow for this criterion. Numerical experiments of the evacuation aimed at a local city in Japan are carried out where tsunami damages are assumed to occur when a big earthquake occurs in the ocean nearby.

Given a directed graph D = (V, A) with a set of d specified vertices S = {s(1),..., s(d)} subset of V and a function f : S -> N where N denotes the set of positive integers, we consider the problem which asks whether there exist Sigma(d)(i=1) f (s(i)) in-trees denoted by T(i,1), T(i,2),..., T(i,f(si)) for every i = 1,..., d such that T(i,1),..., T(i,f(si)) are rooted at s(i), each T(i,j) 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 Sigma(d)(i=1) f(s(i)) and the size of D. Furthermore, for the case where D is acyclic, we present another characterization of the existence of in-trees covering A, and then we prove that in-trees covering A can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs.

This paper presents a simple model of the manufacturing line which focuses on the performance of collision probability, and a method of application to the manufacture of Flat Panel Displays (FPDs) and semiconductors. We derive an approximate formula of the collision probability. When the processing time follows a normal distribution, we also did simulations to evaluate the exact probabilities and confirm that our approximation approach yields reasonable results compared to the simulated results. Moreover, we simplify our approximate formula of the collision probability. Concretely speaking, we derive a closed form formula when the processing time follows an exponential distribution. Finally, we present an optimization problem with the collision probability and show a method to solve it. © 2011 Springer-Verlag Berlin Heidelberg.