Neural Network and Genetic Algorithms for Topology Optimization of the CCS7 Network

The topology optimization of CCS7 network was formulated in Xin and Xu (1998); the A/B plane partition of HSTPs in CCS7 network is discussed here in detail. The problem is proved to be NP-complete, so neural network and genetic algorithms are applied. With test networks generated randomly, the computing results show that the genetic algorithm is quite robust.     

A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs

A graph G is 1-planar if it can be embedded in the plane in such a way that each edge crosses at most one other edge. Borodin showed that 1-planar graphs are 6-colorable, but his proof does not lead to a linear-time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-plane graphs (which are 1-planar graphs already embedded in the plane). The main difficulty in the design of our algorithm comes from the fact that the class of 1-planar graphs is not closed under the operation of edge contraction. This difficulty is overcome by a structural lemma that may be useful in other problems on 1-planar graphs. This paper also shows that it is NP-complete to decide whether a given 1-planar graph is 4-colorable. The complexity of the problem of deciding whether a given 1-planar graph is 5-colorable is still unknown.     

Network interdiction via a Critical Disruption Path: Branch-and-Price algorithms

This paper presents an innovative approach to maximally disconnect a given network. More specifically, this work introduces the concept of a Critical Disruption Path, a path between a source and a destination vertex whose deletion minimizes the cardinality of the largest remaining connected component. Network interdiction models seek to optimally disrupt network operations. Existing interdiction models disrupt network operations by removing vertices or edges. We introduce the first problem and formulation that optimally fragments a network via interdicting a path. Areas of study in which this work can be applied include transportation and evacuation networks, surveillance and reconnaissance operations, anti-terrorism activities, drug interdiction, and counter human-trafficking operations. In this paper, we first address the complexity associated with the Critical Disruption Path problem, and then provide a Mixed-Integer Linear Programming formulation for finding its optimal solution. Further, we develop a tailored Branch-and-Price algorithm that efficiently solves the Critical Disruption Path problem. We demonstrate the superiority of the developed Branch-and-Price algorithm by comparing the results found via our algorithm with the results found via the monolith formulation. In more than half of the test instances that can be solved by both the monolith and our Branch-and-Price algorithm, we outperform the monolith by two orders of magnitude.     

A robust model for finding optimal evolutionary trees

Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species, and seeks to find an edge-weighted treeT in which the distanced _ij ^T in the tree between the leaves ofT corresponding to the speciesi andj exactly equals the observed distance,d _ij . When such a tree exists, this is expressed in the biological literature by saying that the distance function or matrix isadditive, and trees can be constructed from additive distance matrices in0(n ²) time. Real distance data is hardly ever additive, and we therefore need ways of modeling the problem of finding the best-fit tree as an optimization problem.In this paper we present several natural and realistic ways of modeling the inaccuracies in the distance data. In one model we assume that we have upper and lower bounds for the distances between pairs of species and try to find an additive distance matrix between these bounds. In a second model we are given a partial matrix and asked to find if we can fill in the unspecified entries in order to make the entire matrix additive. For both of these models we also consider a more restrictive problem of finding a matrix that fits a tree which is not only additive but alsoultrametric. Ultrametric matrices correspond to trees which can be rooted so that the distance from the root to any leaf is the same. Ultrametric matrices are desirable in biology since the edge weights then indicate evolutionary time. We give polynomial-time algorithms for some of the problems while showing others to be NP-complete. We also consider various ways of fitting a given distance matrix (or a pair of upper- and lower-bound matrices) to a tree in order to minimize various criteria of error in the fit. For most criteria this optimization problem turns out to be NP-hard, while we do get polynomial-time algorithms for some.Supported by DIMACS under NSF Contract STC-88-09648.Supported by NSF Grant CCR-9108969.This work was begun while this author was visiting DIMACS in July and August 1992, and was supported in part by the U.S. Department of Energy under Contract DE-AC04-76DP00789.     

Minimum dominating cycles in outerplanar graphs

Adominating cycle of a graph lies at a distance of at most one from all the vertices of the graph. The problem of finding the minimum size of such a cycle is proved to be difficult even when restricted to planar graphs. An efficient algorithm solving this problem is given for the class of two-connectedouterplanar graphs, in which all vertices lie on the exterior face in a plane embedding of the graph.On leave from Institute of Computer Science, University of Wrocaw, Wrocaw, Poland.     

Integer Programming Models for Deployment of Airport Baggage Screening Security Devices

Aviation security is an important problem of national interest and concern. Baggage screening security devices and operations at airports throughout the United States provide an important defense against terrorist actions targeted at commercial aircraft. Determining where to deploy such devices, and how to best use them can be quite challenging. This paper presents NP-complete decision problems concerning the deployment and utilization of baggage screening security devices. These problems incorporate three different deployment performance measures: uncovered baggage segments, uncovered flight segments, and uncovered passenger segments. Integer programming models are formulated to address optimization versions of these problems and to identify optimal baggage screening security device deployments (i.e., determine the number and type of baggage screening security devices that should be placed at different airports, and determining which baggage should be screened with such devices). The models are illustrated with an example that incorporates data extracted from the Official Airline Guide (OAG).     

On the complexity and algorithm of grooming regular traffic in WDM optical networks

In SONET/WDM networks, a high-speed wavelength channel is usually shared by multiple low-rate traffic demands to make efficient use of the wavelength capacity. The multiplexing is known as traffic grooming and performed by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel is called grooming factor. Since SADMs are expensive, a key optimization goal of traffic grooming is to minimize the total number of SADMs in order to satisfy a given set of traffic demands. As an important communication traffic pattern, all-to-all traffic has been widely studied for the traffic grooming problem. In this paper, we study the regular traffic pattern, which is considered as a generalization of the all-to-all traffic pattern. We focus on the Unidirectional Path-Switched Ring (UPSR) networks. We prove that the traffic grooming problem is NP-hard for the regular traffic pattern in UPSR networks, and show that the problem does not admit a Fully Polynomial Time Approximation Scheme (FPTAS). We further prove that the problem remains NP-hard even if the grooming factor is any fixed value chosen from a subset of integers. We also propose a performance guaranteed algorithm to minimize the total number of required SADMs, and show that the algorithm achieves a better upper bound than previous algorithms. Extensive simulations are conducted, and the empirical results validate that our algorithm outperforms the previous ones in most cases. In addition, our algorithm always uses the minimum number of wavelengths, which are precious resources as well in optical networks.     

Parameterized matching on non-linear structures

The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set Σ. In the parameterized pattern matching model, a consistent renaming of symbols from Σ is allowed in a match. The parameterized matching paradigm has proven useful in problems in software engineering, computer vision, and other applications. In classical pattern matching, both the text and pattern are strings. Applications such as searching in xml or searching in hypertext require searching strings in non-linear structures such as trees or graphs. There has been work in the literature on exact and approximate parameterized matching, as well as work on exact and approximate string matching on non-linear structures. In this paper we explore parameterized matching in non-linear structures. We prove that exact parameterized matching on trees can be computed in linear time for alphabets in an O(n)-size integer range, and in time O(nlogm) in general, where n is the tree size and m the pattern length. These bounds are optimal in the comparison model. We also show that exact parameterized matching on directed acyclic graphs (DAGs) is NP-complete.     

The complexity of induced minors and related problems

The computational complexity of a number of problems concerning induced structures in graphs is studied, and compared with the complexity of corresponding problems concerning non-induced structures. The effect on these problems of restricting the input to planar graphs is also considered. The principal results include: (1) Induced Maximum Matching and Induced Directed Path are NP-complete for planar graphs, (2) for every fixed graphH, InducedH-Minor Testing can be accomplished for planar graphs in time0(n), and (3) there are graphsH for which InducedH-Minor Testing is NP-complete for unrestricted input. Some useful structural theorems concerning induced minors are presented, including a bound on the treewidth of planar graphs that exclude a planar induced minor.The research of the first author was supported by the U.S. Office of Naval Research under Contract N00014-88-K-0456, by the U.S. National Science Foundation under Grant MIP-8603879, and by the National Science and Engineering Research Council of Canada. The second author acknowledges the support of the U.S. Office of Naval Research when visiting the University of Idaho in spring 1990. Some results were also obtained during a visit to the University of Cologne in fall 1990.