A dominating set of a graph G is a set S subset of V(G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is co...
详细信息
A dominating set of a graph G is a set S subset of V(G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number, denoted by gamma(c)(G). Zhuang showed that gamma(c)(G) of a maximal outerplanar graph G is bounded by min{left perpendicular n+k/2 right perpendicular - 2, left perpendicular 2(n-k)/3 right perpendicular} (Zhuang, 2020), where k is the number of 2-degree vertices in G. In this paper, we give an algorithm for finding a connected dominating set of maximal outerplanar graphs and get an upper bound gamma(c)(G) <= left perpendicular n-k+x/2 right perpendicular, where x is a counter in the algorithm and x <= k - 2. As a corollary, the result that gamma(c)(G) <= left perpendicular n-2/2 right perpendicular for a maximal outerplanar G is gotten directly. This results is better than the above known bound for 3 < k < n+6/4. In addition, we complement some analysis with simulations to evaluate the advantages of our results. (C) 2022 Elsevier B.V. All rights reserved.
We present a new algorithm for the fast and reliable structure prediction of synthetic receptor-ligand complexes. Our method is based on the protein-ligand docking program FlexX and extends our recently introduced doc...
详细信息
We present a new algorithm for the fast and reliable structure prediction of synthetic receptor-ligand complexes. Our method is based on the protein-ligand docking program FlexX and extends our recently introduced docking technique for synthetic receptors, which has been implemented in the program FlexR. To handle the flexibility of the relevant molecules, we apply a novel docking strategy that uses an adaptive two-sided incremental construction algorithm which incorporates the structural flexibility of both the ligand and synthetic receptor. We follow an adaptive strategy, in which one molecule is expanded by attaching its next fragment in all possible torsion angles, whereas the other (partially assembled) molecule serves as a rigid binding partner. Then the roles of the molecules are exchanged. Geometric filters are used to discard partial conformations that cannot realize a targeted interaction pattern derived in a graph-based precomputation phase. The process is repeated until the entire complex is built up. Our algorithm produces promising results on a test data set comprising 10 complexes of synthetic receptors and ligands. The method generated near-native solutions compared to crystal structures in all but one case. It is able to generate solutions within a couple of minutes and has the potential of being used as a virtual screening tool for searching for suitable guest molecules for a given synthetic receptor in large databases of guests and vice versa.
The transit network design problem (TNDP) aims to determine a set of bus routes for a public transportation system, which must be convenient from the viewpoints of both users (people who use public transportation) and...
详细信息
The transit network design problem (TNDP) aims to determine a set of bus routes for a public transportation system, which must be convenient from the viewpoints of both users (people who use public transportation) and operators (companies who own the resources to give the service). This article presents a constructive algorithm for the TNDP. It is specially designed to produce a set of routes that fulfils demand covering constraints, while taking into account the interests of both users and operators. Its general structure is inspired in the Route Generation algorithm (RGA) of Baaj and Mahmassani, where its original expansion of routes by inserting individual vertices is replaced by a strategy of insertion of pairs of vertices. The algorithm proposed, called Pair Insertion algorithm (PIA) can be used to generate initial solutions for a local improvement or evolutionary algorithm, as well as to complete an unfeasible solution with respect to demand covering constraints. Numerical results comparing PIA with RGA over a real test case show that both algorithms produce solutions with similar quality from the users viewpoint (in terms of in-vehicle travel time), while the former produces better solutions from the operators viewpoint (in terms of number of routes and total route duration) and requires a higher execution time. Since the TNDP arises in a context of strategic planning, a solution that reduces the operation cost of the system is highly desirable, even though it takes more time to be computed. The experimental study of the proposed algorithm also shows its ability to produce diverse solutions in both decision and objective spaces;this is a useful property when looking at the use of PIA as a subroutine in the context of another algorithm such as metaheuristics, in particular for a multi-objective problem like TNDP. (c) 2008 Elsevier Ltd. All rights reserved.
Recently, a constructive algorithm based on asymptotic expansions was proposed for computing water waves of large amplitude, in the absence of stagnation points, by one of the authors in Kalimeris (Real World Appl Non...
详细信息
Recently, a constructive algorithm based on asymptotic expansions was proposed for computing water waves of large amplitude, in the absence of stagnation points, by one of the authors in Kalimeris (Real World Appl Nonlinear Anal 37:182-212, 2017). Here, we perform a numerical implementation of this algorithm, verifying the analytical results and, indeed, computing large amplitude waves. Furthermore, we introduce a modification of the existing analytical procedure, which allows the computation of waves with variable vorticity by a straightforward adaptation of the current algorithm. Profiles and other features of water waves are presented for constant and some cases of variable vorticity.
This paper focuses on the problem of determining a permutation schedule for n jobs in an m-machine flow shop that operates in a sequence-dependent setup time (SDST) environment. Two constructive heuristic algorithms a...
详细信息
This paper focuses on the problem of determining a permutation schedule for n jobs in an m-machine flow shop that operates in a sequence-dependent setup time (SDST) environment. Two constructive heuristic algorithms are developed with the minimisation of makespan as the objective. The first heuristic algorithm termed as setup ranking algorithm obtains the sequence using the setup times of jobs only. The second heuristic algorithm, fictitious job setup ranking algorithm (FJSRA), is developed using the concept of fictitious jobs. Pairs of jobs with minimum setup time between them constitute the fictitious jobs. Both these algorithms are compared with an existing constructive algorithm. For the purpose of experimentation, Taillard benchmark problems are used to develop SDST benchmark problems at eight different levels of sequence-dependent setup times. Graphical analysis, relative performance index analysis and statistical analysis are carried out on the results obtained for all the eight sets of benchmark problems. The analysis reveals that FJSRA emerges as the better algorithm for larger problems and for smaller problems with higher level of setup time. The results of statistical analysis are used to develop setup time dominance matrix for deciding upon the algorithm to be used for a particular size of problem.
This paper presents a novel hybrid algorithm for feedforward neural networks, called a self organizing map-based initialization for hybrid training based on a two stage learning approach. First stage, a structure lear...
详细信息
This paper presents a novel hybrid algorithm for feedforward neural networks, called a self organizing map-based initialization for hybrid training based on a two stage learning approach. First stage, a structure learning scheme which includes adding hidden neurons is used to determine the network size. Second stage, a FN (fuzzy neighborhood)-based hybrid learning scheme which we have recently proposed is used to adjust the network parameters. In this approach the weights between input and hidden layers are firstly adjusted by Kohonen algorithm with fuzzy neighborhood, whereas the weights connecting hidden and output layers are adjusted using gradient descent method. Four simulation examples are provided to demonstrate the efficiency of the approach compared with other well-known and recently proposed learning methods. (C) 2011 Elsevier B.V. All rights reserved.
Checkerboard patterns belong to a special class of 2-stage guillotine patterns that require less machine time to be cut. In this paper we propose an enumerative algorithm to generate exact constrained checkerboard pat...
详细信息
Checkerboard patterns belong to a special class of 2-stage guillotine patterns that require less machine time to be cut. In this paper we propose an enumerative algorithm to generate exact constrained checkerboard patterns. At each node of the enumeration tree a constructive procedure is used to generate a feasible pattern. In addition, an upper bound on the objective function value is calculated to decide whether further branching from the node is worth. The algorithm was implemented and computational tests were performed. The test results indicate that the proposed scheme outperforms previous methods of the literature in terms of execution times. (c) 2006 Published by Elsevier Ltd.
Feature construction has been shown to be an useful technique to improve the efficiency of extracting information from raw data. We develop a modified feature construction algorithm, using correlation information amon...
详细信息
Feature construction has been shown to be an useful technique to improve the efficiency of extracting information from raw data. We develop a modified feature construction algorithm, using correlation information among the initial set of features, and study its performance. Feed-forward neural networks, using the back-propagation algorithm to learn, have been shown to have excellent properties while plagued with the problem of time needed to learn concepts. We alleviate this inherent problem with the back-propagation algorithm using data pre-processed by the proposed feature construction algorithm. Initial results suggest that this methodology can be beneficially used along with other means of improving the learning performance in feed-forward neural networks.
This paper describes the cascade neural network design algorithm (CNNDA), a new algorithm for designing compact, two-hidden-layer artificial neural networks (ANNs). This algorithm determines an ANN's architecture ...
详细信息
This paper describes the cascade neural network design algorithm (CNNDA), a new algorithm for designing compact, two-hidden-layer artificial neural networks (ANNs). This algorithm determines an ANN's architecture with connection weights automatically. The design strategy used in the CNNDA was intended to optimize both the generalization ability and the training time of ANNs. In order to improve the generalization ability, the CNDDA uses a combination of constructive and pruning algorithms and bounded fan-ins of the hidden nodes. A new training approach, by which the input weights of a hidden node are temporarily frozen when its output does not change much after a few successive training cycles, was used in the CNNDA for reducing the computational cost and the training time. The CNNDA was tested on several benchmarks including the cancer, diabetes and character-recognition problems in ANNs. The experimental results show that the CNNDA can produce compact ANNs with good generalization ability and short training time in comparison with other algorithms. (C) 2001 Elsevier Science Ltd. All rights reserved.
In this article we derive a complete characterization of the Solvent Excluded Surface (SES) for molecular systems including a complete characterization of singularities of the surface. The theory is based on an implic...
详细信息
In this article we derive a complete characterization of the Solvent Excluded Surface (SES) for molecular systems including a complete characterization of singularities of the surface. The theory is based on an implicit representation of the SES, which, in turn, is based on the signed distance function to the Solvent Accessible Surface (SAS). All proofs are constructive so that the theory allows for efficient algorithms in order to compute the area of the SES and the volume of the SES-cavity, or to visualize the surface. Further, we propose to refine the notion of SAS and SES in order to take inner holes in a solute molecule into account or not. (C) 2016 Elsevier Inc. All rights reserved.
暂无评论