A novel framework has recently been proposed for designing the molecular structure of chemical compounds with a desired chemical property using both artificial neural networks and mixed integer linear programming. In this paper, we design a new method for inferring a polymer based on the framework. For this, we introduce a new way of representing a polymer as a form of monomer and define new descriptors that feature the structure of polymers. We also use linear regression as a building block of constructing a prediction function in the framework. The results of our computational experiments reveal a set of chemical properties on polymers to which a prediction function constructed with linear regression performs well. We also observe that the proposed method can infer polymers with up to 50 non-hydrogen atoms in a monomer form.

A novel framework for designing the molecular structure of chemical compounds with a desired chemical property has recently been proposed. The framework infers a desired chemical graph by solving a mixed integer linear program (MILP) that simulates the computation process of two functions: a feature function defined by a two-layered model on chemical graphs and a prediction function constructed by a machine learning method. To improve the learning performance of prediction functions in the framework, we design a method that splits a given data set$\mathcal {C}$into two subsets$\mathcal {C}^{(i)},i=1,2$by a hyperplane in a chemical space so that most compounds in the first (resp., second) subset have observed values lower (resp., higher) than a threshold$\theta$. We construct a prediction function$\psi$to the data set$\mathcal {C}$by combining prediction functions$\psi _{i},i=1,2$each of which is constructed on$\mathcal {C}^{(i)}$independently. The results of our computational experiments suggest that the proposed method improved the learning performance for several chemical properties to which a good prediction function has been difficult to construct.

Abstract Intelligent systems are applied in a wide range of areas, and computer-aided drug design is a highly important one. One major approach to drug design is the inverse QSAR/QSPR (quantitative structure-activity and structure-property relationship), for which a method that uses both artificial neural networks (ANN) and mixed integer linear programming (MILP) has been proposed recently. This method consists of two phases: a forward prediction phase, and an inverse, inference phase. In the prediction phase, a feature function f over chemical compounds is defined, whereby a chemical compound G is represented as a vector f(G) of descriptors. Following, for a given chemical property $$\pi$$ , using a dataset of chemical compounds with known values for property $$\pi$$ , a regressive prediction function $$\psi$$ is computed by an ANN. It is desired that $$\psi (f(G))$$ takes a value that is close to the true value of property $$\pi$$ for the compound G for many of the compounds in the dataset. In the inference phase, one starts with a target value $$y^*$$ of the chemical property $$\pi$$ , and then a chemical structure $$G^*$$ such that $$\psi (f(G^*))$$ is within a certain tolerance level of $$y^*$$ is constructed from the solution to a specially formulated MILP. This method has been used for the case of inferring acyclic chemical compounds. With this paper, we propose a new concept on acyclic chemical graphs, called a skeleton tree, and based on it develop a new MILP formulation for inferring acyclic chemical compounds. Our computational experiments indicate that our newly proposed method significantly outperforms the existing method when the diameter of graphs is up to 8. In a particular example where we inferred acyclic chemical compounds with 38 non-hydrogen atoms from the set {C, O, S} times faster.

Drug discovery is one of the major goals of computational biology and bioinformatics. A novel framework has recently been proposed for the design of chemical graphs using both artificial neural networks (ANNs) and mixed integer linear programming (MILP). This method consists of a prediction phase and an inverse prediction phase. In the first phase, an ANN is trained using data on existing chemical compounds. In the second phase, given a target chemical property, a feature vector is inferred by solving an MILP formulated from the trained ANN and then a set of chemical structures is enumerated by a graph enumeration algorithm. Although exact solutions are guaranteed by this framework, the types of chemical graphs have been restricted to such classes as trees, monocyclic graphs, and graphs with a specified polymer topology with cycle index up to 2. To overcome the limitation on the topological structure, we propose a new flexible modeling method to the framework so that we can specify a topological substructure of graphs and a partial assignment of chemical elements and bond-multiplicity to a target graph. The results of computational experiments suggest that the proposed system can infer chemical graphs with around up to 50 non-hydrogen atoms.

A novel framework has recently been proposed for designing the molecular structure of chemical compounds with a desired chemical property using both artificial neural networks and mixed integer linear programming. In the framework, a chemical graph with a target chemical value is inferred as a feasible solution of a mixed integer linear program that represents a prediction function and other requirements on the structure of graphs. In this paper, we propose a procedure for generating other feasible solutions of the mixed integer linear program by searching the neighbor of output chemical graph in a search space. The procedure is combined in the framework as a new building block. The results of our computational experiments suggest that the proposed method can generate an additional number of new chemical graphs with up to 50 non-hydrogen atoms.

We are given an instance (G,I,sigma) with a graph G=(V,E), a set I of items, and a function sigma:V -> 2^I. For a subset X of V, let G[X] denote the subgraph induced from G by X, and I_sigma(X) denote the common item set over X. A subset X of V such that G[X] is connected is called a connector if, for any vertex v in V\X, G[X cup {v}] is not connected or I_sigma(X cup {v}) is a proper subset of I_sigma(X). In this paper, we present the first polynomial-delay algorithm for enumerating all connectors. For this, we first extend the problem of enumerating connectors to a general setting so that the connectivity condition on X in G can be specified in a more flexible way. We next design a new algorithm for enumerating all solutions in the general setting, which leads to a polynomial-delay algorithm for enumerating all connectors for several connectivity conditions on X in G, such as the biconnectivity of G[X] or the k-edge-connectivity among vertices in X in G.

Enumerating chemical compounds with given structural properties plays an important role in structure elucidation, with applications such as drug design. We focus on the problem of enumerating tree-like chemical graphs specified by upper and lower bounds on feature vectors, where chemical graphs represent compounds, and a feature vector characterizes frequencies of finite paths in a graph. Building on the branch-and-bound algorithm proposed in earlier work, we propose a new bounding procedure, called Resource Cut, to speed up the enumeration process. Tree-like chemical graphs are modeled as vertex-colored trees, colors representing chemical elements. The algorithm is based on a scheme of generating each unique colored tree with a specified number n of vertices. A colored tree is constructed by repeatedly appending vertices. Given a set R of n colored vertices, we found that the algorithm often constructs trees that cannot be extended to a unique representation of a colored tree no matter how the remaining unused colored vertices in the set R are appended. We derive a mathematical condition to detect and discard such trees. Experimental results show that Resource Cut significantly reduces the search space. We have been able to obtain exact numbers of chemical graphs with up to 17 vertices excluding hydrogen atoms.

In the bounded-degree cut problem, we are given a multigraph G=(V,E), two disjoint vertex subsets A,B subseteq V, two functions u_A, u_B:V -> {0,1,...,|E|} on V, and an integer k >= 0. The task is to determine whether there is a minimal (A,B)-cut (V_A,V_B) of size at most k such that the degree of each vertex v in V_A in the induced subgraph G[V_A] is at most u_A(v) and the degree of each vertex v in V_B in the induced subgraph G[V_B] is at most u_B(v). In this paper, we show that the bounded-degree cut problem is fixed-parameter tractable by giving a 2^{18k}|G|^{O(1)}-time algorithm. This is the first single exponential FPT algorithm for this problem. The core of the algorithm lies two new lemmas based on important cuts, which give some upper bounds on the number of candidates for vertex subsets in one part of a minimal cut satisfying some properties. These lemmas can be used to design fixed-parameter tractable algorithms for more related problems.

Enumeration of chemical structures is useful for drug design, which is one of the main targets of computational biology and bioinformatics. A chemical graph with no other cycles than benzene rings is called tree-like, and becomes a tree possibly with multiple edges if we contract each benzene ring into a single virtual atom of valence 6. All tree-like chemical graphs with a given tree representation are called the substituted benzene isomers of . When we replace each virtual atom in with a benzene ring to obtain a substituted benzene isomer, distinct isomers of are caused by the difference in arrangements of atom groups around a benzene ring. In this paper, we propose an efficient algorithm that enumerates all substituted benzene isomers of a given tree representation . Our algorithm first counts the number of all the isomers of the tree representation by a dynamic programming method. To enumerate all the isomers, for each , our algorithm then generates the th isomer by backtracking the counting phase of the dynamic programming. We also implemented our algorithm for computational experiments.

In this paper, we study the problem of finding an integral multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative integer edge capacity and a set of terminals. In general, it is known that the flow value of an integral multiflow is bounded by the cut value of a cut-system which consists of disjoint subsets each of which contains exactly one terminal or has an odd cut value, and there exists a pair of an integral multiflow and a cut-system whose flow value and cut value are equal; i.e., a pair of a maximum integral multiflow and a minimum cut. In this paper, we propose an O(n)-time algorithm that finds such a pair of an integral multiflow and a cut-system in a given tree instance with n vertices. This improves the best previous results by a factor of Omega(n). Regarding a given tree in an instance as a rooted tree, we define O(n) rooted tree instances taking each vertex as a root, and establish a recursive formula on maximum integral multiflow values of these instances to design a dynamic programming that computes the maximum integral multiflow values of all O(n) rooted instances in linear time. We can prove that the algorithm implicitly maintains a cut-system so that not only a maximum integral multiflow but also a minimum cut-system can be constructed in linear time for any rooted instance whenever it is necessary. The resulting algorithm is rather compact and succinct.

BACKGROUND: Enumeration of chemical graphs satisfying given constraints is one of the fundamental problems in chemoinformatics and bioinformatics since it leads to a variety of useful applications including structure determination of novel chemical compounds and drug design. RESULTS: In this paper, we consider the problem of enumerating all tree-like chemical graphs from a given set of feature vectors, which is specified by a pair of upper and lower feature vectors, where a feature vector represents the frequency of prescribed paths in a chemical compound to be constructed. This problem can be solved by applying the algorithm proposed by Ishida et al. to each single feature vector in the given set, but this method may take much computation time because in general there are many feature vectors in a given set. We propose a new exact branch-and-bound algorithm for the problem so that all the feature vectors in a given set are handled directly. Since we cannot use the bounding operation proposed by Ishida et al. due to upper and lower constraints, we introduce new bounding operations based on upper and lower feature vectors, a bond constraint, and a detachment condition. CONCLUSIONS: Our proposed algorithm is useful for enumerating tree-like chemical graphs with given upper and lower bounds on path frequencies.

Given a system $(V,f,d)$ on a finite set V consisting of two set functions $f:2^V\to\mathbb{R}$ and $d:2^V\to\mathbb{R}$, we consider the problem of finding a set $R\subseteq V$ of minimum cardinality such that $f(X)\ge d(X)$ for all $X\subseteq V-R$, where the problem can be regarded as a natural generalization of the source location problems and the external network problems in (undirected) graphs and hypergraphs. We give a structural characterization of minimal deficient sets of $(V,f,d)$ under certain conditions. We show that all such sets form a tree hypergraph if f is posimodular and d is modulotone (i.e., each nonempty subset X of V has an element $v\in X$ such that $d(Y)\ge d(X)$ for all subsets Y of X that contain v) and that, conversely, any tree hypergraph can be represented by minimal deficient sets of $(V,f,d)$ for a posimodular function f and a modulotone function d. By using this characterization, we present a polynomial-time algorithm if, in addition, f is submodular and d is given by either $d(X)=\max\{p(v)\mid v\in X\}$ for a function $p:V\to\RR_+$ or $d(X)=\max\{r(v,w)\mid v\in X,w\in V-X\}$ for a function $r:V^2\to\mathbb{R}_+$. Our result provides first polynomial-time algorithms for the source location problem in hypergraphs and the external network problems in graphs and hypergraphs. We also show that the problem is intractable, even if f is submodular and $d\equiv\mathbf{0}$.

Let $G=(V,E)$ be an edge‐weighted undirected graph with n vertices and m edges. We present a deterministic algorithm to compute a minimum k‐way cut of G for a given k. Our algorithm is a divide‐and‐conquer method based on a procedure that reduces an instance of the minimum k‐way cut problem to $O(n^{2k-5})$ instances of the minimum $(\lfloor (k+\sqrt{k})/2\rfloor+1)$‐way cut problem, and can be implemented to run in $O(n^{4k/(1-1.71/\sqrt{k}) -31} )$ time. With a slight modification, the algorithm can find all minimum k‐way cuts in $O(n^{4k/(1-1.71/\sqrt{k}) -16} )$ time.

This paper proposes a contention-free burst scheduling scheme in optically burst-switched WDM networks. We construct contention-free wavelength planes (lambda-planes) by assigning dedicated wavelengths to each ingress node. Bursts are transmitted to their egress nodes on lambda-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 buffer. This paper develops a spanning tree construction algorithm, aiming at balancing input loads among output ports at each ingress node. Further 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.

Abstract We consider two variants of the single‐vehicle scheduling problem on line‐shaped networks. Let L = (V, E) be a line, where V = {v1, v2, … , vn} is a set of n vertices and E = {{vi, vi+1}|i = 1, 2, … , n − 1} is a set of edges. The travel times w(u, v) and w(v, u) are associated with each edge {u, v} ∈ E, and each job, which is also denoted as v and is located at vertex v ∈ V, has release time r(v) and handling time h(v). There is a single vehicle, which is initially situated at v1 ∈ V, and visits all vertices to process the jobs before it returns back to v1. The first problem asks to find an optimal routing schedule of the vehicle that minimizes the completion time. This is NP‐hard [21], and there exists an approximate algorithm with the approximation ratio of 2 [12]. In this paper, we improve this ratio to 1.5. On the other hand, the second problem minimizes the maximum lateness, under the assumption that all release times r(v) are zero, but there are due times d(v) for v ∈ V and d(vn+1) for the vehicle. This problem is also NP‐hard [13]. We improve the previous best‐known approximation ratio of 2, which was obtained in [11], to 1.5. © 2002 Wiley Periodicals, Inc.

Abstract Given an undirected multigraphG= (V,E) and a requirement functionrλ: ( ) →Z+(where ( ) is the set of all pairs of vertices andZ+is the set of nonnegative integers), we consider the problem of augmentingGby the smallest number of new edges so that the local edge‐connectivity and vertex‐connectivity between every pairx,y∈Vbecome at leastrλ(x,y) and two, respectively. In this paper, we show that the problem can be solved inO(n3(m+n) log(n2/(m+n))) time, wherenandmare the numbers of vertices and pairs of adjacent vertices inG, respectively. This time complexity can be improved toO((nm+n2logn) logn), in the case of the uniform requirementrλ(x,y)= 𝓁 for allx,y∈V. Furthermore, for the generalrλ, we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed 𝓁*= max{rλ(x,y) |x,y∈V}. © 2001 John Wiley & Sons, Inc.

Let G be an Eulerian digraph, and let {x1, x2}, {y1,y2} be two pairs of vertices in G. A directed path from a vertex s to a vertex t is called an st-path. An instance (G;{x1, x2}, {y1,y2}) is called feasible if there is a choice of h,i,j,k with {h,i} = {j,k} = {1,2} such that G has two arc-disjoint xhxi- and yjyk-paths. In this paper, we characterize the structure of minimal infeasible instances, based on which an O(m+nlog n) time algorithm is presented to decide whether a given instance is feasible, where n and m are the number of vertices and arcs in the instance, respectively. If the instance is feasible, the corresponding two arc-disjoint paths can be computed in O(m(m+nlog n)) time.

Let $\lambda({\cal N})$ denote the weight of a minimum cut in an edge-weighted undirected network ${\cal N}$, and n and m denote the numbers of vertices and edges, respectively. It is known that $O(n^{2k})$ is an upper bound on the number of cuts with weights less than $k\lambda({\cal N})$, where $k\geq 1$ is a given constant. This paper first shows that all cuts of weights less than $k\lambda({\cal N})$ can be enumerated in $O(m^2n+n^{2k}m)$ time without using the maximum flow algorithm. The paper then proves for $k < \four$ that $n\choose 2$ is a tight upper bound on the number of cuts of weights less than $k\lambda({\cal N})$, and that all those cuts can be enumerated in $O(m^2n+mn^2\log n)$ time.

Article Free Access Share on Deterministic Õ(nm) time edge-splitting in undirected graphs Authors: Hiroshi Nagamochi Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01 Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01View Profile , Toshihide Ibaraki Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01 Dept. Applied Mathematics and Physics, Kyoto University, Kyoto, Japan 606-01View Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 64–73https://doi.org/10.1145/237814.237830Published:01 July 1996Publication History 7citation291DownloadsMetricsTotal Citations7Total Downloads291Last 12 Months16Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract A cut‐set in an undirected multigraph G is a subset of edges whose removal makes the graph disconnected. Let mi(G) denote the number of all cut‐sets, each of which consists of i edges. In this paper, for any multigraph G with n nodes and e (⩾3n/2) edges, we show that mi(G) with α ⩽ i ⩽ 2(α ‐ γ) ‐ 3, where α = ⌊2e/n⌋ and γ = ⌊2e/n(n ‐ 1)⌋, is greater than or equal to (\documentclass{article}\pagestyle{empty}\begin{document}$ \left({\matrix{ {e - \alpha } \cr {i - \alpha } \cr } } \right) $\end{document} )((α + 1)n ‐ 2e) + (\documentclass{article}\pagestyle{empty}\begin{document}$ \matrix{ {e - \alpha - 1} \cr {i - \alpha - 1} \cr } $\end{document} )(2e ‐αn). A necessary and sufficient condition for a multigraph G with given n and e to minimize mi(G) for an i with i ⩽ 2(α ‐ γ) ‐ 3 is presented. We also show that there exists a graph such that the lower bound is tight for all i in the range [α, 2(α ‐ γ) ‐ 3]. © 1994 by John Wiley & Sons, Inc.

Although finding an optimal coterie for a general graph G is computationally intractable, it is shown that it can be easily found if G is a ring. Since the solution is already known when G is a complete graph, it is implied that an optimal coterie can be obtained if every biconnected component of G consists of a single edge, a ring, or a complete graph.>

Given an undirected graph $G = ( V,E )$, it is known that its edge-connectivity $\lambda ( G )$ can be computed by solving $O( | V | )$ max-flow problems. The best time bounds known for the problem are $O( \lambda ( G ) | V |^2 )$, due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and $O( | E |^{3/2} | V | )$, due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple. An $O( | E | + \min \{ \lambda ( G ) | V |^2 ,p | V | + | V |^2 \log | V | \} )$ time algorithm for computing the edge-connectivity $\lambda ( G )$ of a multigraph $G = ( V,E )$, where $p ( \leqq | E | )$ is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of $| V |$ times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in $O ( | V | | E | + | V |^2 \log | V | )$ time.

Abstract The reliability of capacitated networks subject to random arc failures is evaluated by the expected value of maximum flow. It is known that calculating the expected value of maximum flow is NP‐hard, but a lower bound can be efficiently computed by the method of Carey and Hendrickson. This bound sometimes gives the exact value, e.g., if graphs are bipartite. In this article, for directed and undirected networks, respectively, we give necessary and sufficient conditions for the above lower bound to provide the exact value.

Abstract We study the multicommodity flow problem that minimizes a strictly convex cost objective function subject to the capacity constraints on individual commodities as well as the total flows in each arc. By making use of its dual, we formulate the problem as a nonlinear unconstrained optimization problem and propose relaxation methods. Computational results show that the proposed methods can practically solve problem instances, for example, with up to 100 nodes, 1000 arcs, and seven commodities.