Given an edge-weighted bipartite digraph G=(A,B;E), the Bipartite Traveling Salesman Problem (BTSP) asks to find the minimum cost of a Hamiltonian cycle of G, or determine that none exists. When |A|=|B|=n, the BTSP can be solved using polynomial space in O*(42nnlog n) time by using the divide-and-conquer algorithm of Gurevich and Shelah (SIAM Journal of Computation, 16(3), pp.486-502, 1987). We adapt their algorithm for the bipartite case, and show an improved time bound of O*(42n), saving the nlog n factor.

Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average.

We consider the problem of finding a minimum weight k-connected spanning subgraph of a given edge-weighted graph G for k=3. The problem is known to be NP-hard for k 2, and there are an O(n2m) time 3-approximation algorithm due to Nutov and Penn and an O(n8) time 2-approximation algorithm due to Dinitz and Nutov, where n and m are the numbers of vertices and edges in G, respectively. In this paper, we present a 7/3-approximation algorithm which runs in O(n2m) time.

Given a graph G = (V,E) together with a nonnegative integer requirement on vertices r:V Z+, the annotated edge dominating set problem is to find a minimum set M ⊆ E such that, each edge in E - M is adjacent to some edge in M, and M contains at least r(v) edges incident on each vertex v ∈ V. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree 3 can be solved in O*(1.2721n) time and polynomial space, where n is the number of vertices in the graph. We also show that there is an O*(2.2306k)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an annotated edge dominating set of size k or not.

For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAGs,t that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.

In this paper, we briefly review kernel methods for analysis of chemical compounds with focusing on the authors' works. We begin with a brief review of existing kernel functions that are used for classification of chemical compounds and prediction of their activities. Then, we focus on the pre-image problem for chemical compounds, which is to infer a chemical structure that is mapped to a given feature vector, and has a potential application to design of novel chemical compounds. In particular, we consider the pre-image problem for feature vectors consisting of frequencies of labeled paths of length at most K. We present several time complexity results that include: NP-hardness result for a general case, polynomial time algorithm for tree structured compounds with fixed K, and polynomial time algorithm for K=1 based on graph detachment. Then we review practical algorithms for the pre-image problem, which are based on enumeration of chemical structures satisfying given constraints. We also briefly review related results which include efficient enumeration of stereoisomers of tree-like chemical compounds and efficient enumeration of outerplanar graphs.

We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG, by replacing each hyperedge e={v1,,vk} with a new vertex we and k edges {we, v1},, {we, vk}, we define an SNDP or ECP in the resulting graph. We show that by approximately solving the SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a dmax+-approximation algorithm for the SNDPHG with dmax 3, where dmax (resp. dmax+) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a dmax+(rmax)-approximation algorithm for the SNDPHG, where (i)=j=1i(1/j) is the harmonic function and rmax is the maximum connectivity requirement.

In this paper, we consider a collision detection problem of spheres which asks to detect all pairs of colliding spheres in a set of n spheres located in d-dimensional space. We propose a collision detection algorithm for spheres based on slab partitioning technique and a plane sweep method. We derive a theoretical upper bound on the time complexity of the algorithm. Our bound tells that if both the dimension and the maximum ratio of radii of two spheres are bounded, then our algorithm runs in O(n log n + K) time with O(n + K) space, where K denotes the number of pairs of colliding spheres.

We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.

The method of constructing a graph G with the maximum cardinality of minimum cut-sets, which is 2e/n, has been obtained by Harary in 1962, where n is the number of nodes and e is the number of edges. Afterward, the problem of finding a simple graph G which minimizes the number of minimum cut-sets with cardinality 2e/n subject to λ(G)2e/n was solved by Bauer, Boesch, Suffel and Tindell in 1985. Generalizing this, a necessary and sufficient condition for a simple graph with n nodes and e edges to minimize the number of cut-sets with cardinality z has been recently presented by Sun, Nagamochi and Kusunoki in 1989, where z is chosen such that 2e/nz22e/n3 for2e/n3, or z2, 3, for2e/n2. In this paper, we generalize the above results to multiple graphs, and give a necessary and sufficient condition for a multiple graph G with n nodes and e edges to minimize the number of minimum cut-sets whose cardinality is2e/n.

Let G = (V,E) be an edge weighted graph with n vertices and m edges. For a given integer p with 1 < p < n, we call a set X V of p vertices a p-maximizer if X has a property that the edge-connectivity of the graph obtained by contracting X into a single vertex is no less than that of the graph obtained by contracting any other subset of p vertices. In this paper, we first show that there always exists an ordering v1,v2,...,vn of vertices in V such that, for each i = 2,3,...,n - 1, set {v1,v2,...,vi} is an i-maximizer. We give an O(mn + n2log n) time algorithm for finding such an ordering and then show an application to the source location problem.

It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.

In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.

In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n ≥ 3 and g ≥ 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.

Let H be a graph with a designated vertex s, where edges are weighted by nonnegative reals. Splitting edges e={u,s} and e'={s,v} at s is an operation that reduces the weight of each of e and e' by a real δ>0 while increasing the weight of edge {u,v} by δ. It is known that all edges incident to s can be split off while preserving the edge-connectivity of H and that such a complete splitting is used to solve many connectivity problems. In this paper, we give an O(mn+n2log n) time algorithm for finding a complete splitting in a graph with n vertices and m edges.

Let G be a connected graph in which we designate a vertex or a block (a biconnected component) as the center of G. For each cut-vertex v, let Gv be the connected subgraph induced from G by v and the vertices that will be separated from the center by removal of v, where v is designated as the root of Gv. We consider the set R of all such rooted subgraphs in G, and assign an integer, called an index, to each of the subgraphs so that two rooted subgraphs in R receive the same indices if and only if they are isomorphic under the constraint that their roots correspond each other. In this paper, assuming a procedure for computing a signature of each graph in a class of biconnected graphs, we present a framework for computing indices to all rooted subgraphs of a graph G with a center which is composed of biconnected components from . With this framework, we can find indices to all rooted subgraphs of a outerplanar graph with a center in linear time and space.

The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.

Let G = (V,E) be a connected graph such that each edge e ∈ E and each vertex v ∈ V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X1,X2,...,Xp of V and a set of p subtrees T1,T2,...,Tp such that each Ti contains Xi∪{r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in Ti and the weights of vertices in Xi. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X1,X2,...,Xp} of V and a set of p cycles C1,C2,...,Cp such that Ci contains Xi∪{r} so as to minimize the maximum cost of the cycles, where the cost of Ci is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G,w).

This paper proposes a contention-free burst scheduling scheme for optically burst-switched WDM networks. We construct contention-free wavelength planes (λ-planes) by assigning dedicated wavelengths to each ingress node. Bursts are transmitted to their egress nodes on λ-planes, along routes forming a spanning tree. As a result, contention at intermediate core nodes is completely eliminated, and contention at ingress nodes is resolved by means of electric buffers. This paper develops a spanning tree construction algorithm, aiming at balancing input loads among output ports at each ingress node. Furthermore, a wavelength assignment algorithm is proposed, which is based on the amount of traffic lost at ingress nodes. We show that the proposed scheme can decrease the burst loss probability drastically, even if traffic intensities at ingress nodes are different.

Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size µ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size ⌈µ(G)/2⌉ or not. In this paper, we prove that the problem is NP-complete, whereas we design an O*(2.0801µ(G)/2)-time and polynomial-space algorithm to the problem.