Search

Abstract: The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers for subsequent queries of the form: “Given indices i, j, what is the index of the minimum value of ?” This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: “Given indices i and j, what is the maximum-sum segment of ?” We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper. [Copyright &y& Elsevier]

Abstract: A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59–73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such that is a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such that is a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that is a tree. [Copyright &y& Elsevier]

Abstract: Let be a graph of order , minimum degree and connectivity . Chartrand and Harary [Graphs with prescribed connectivities, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 61–63] gave the following lower bound on the connectivityTopp and Volkmann [Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695–700] improved this bound to , if is bipartite and . In this paper, we show that this result remains valid for diamond-free graphs with . A diamond is a graph obtained from a complete graph with 4 vertices by removing an arbitrary edge. Furthermore, we show that the above bounds can be improved significantly for graphs with and no 4-cycle, namely, if , thenFor graphs that, in addition, contain no 3-cycle, we improve this bound even further. [Copyright &y& Elsevier]

Abstract: The discovery of the first fullerene has raised an interest in the study of other candidates for modelling of carbon molecules. As a generalization of the fullerenes, fulleroids are defined as cubic convex polyhedra with all the faces of size five or greater. In this paper, we give necessary and sufficient condition for the existence of fulleroids with only pentagonal and -gonal faces and with the symmetry group isomorphic to the full symmetry group of the regular octahedron. The existence is proved by finding infinite series of examples. The nonexistence is proved using symmetry invariants. [Copyright &y& Elsevier]

Abstract: Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link on the cycle is used at most times, each hyperedge has its profit and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC). In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link has same capacity k, we propose an algorithm with approximation ratio . [Copyright &y& Elsevier]

Abstract: For a given graph G of order n, a k--labelling is defined as a function such that when and when . The -labelling number of G, denoted by , is the smallest number k such that G has a k--labelling. The hole index of G is the minimum number of integers not used in a --labelling of G. We say G is full-colorable if ; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with and , where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole -colorings, Discrete Appl. Math. 130 (2003) 513–519]. [Copyright &y& Elsevier]

Abstract: The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems. [Copyright &y& Elsevier]

Abstract: A Skolem sequence is a sequence (where , each occurs exactly twice in the sequence and the two occurrences are exactly positions apart. A set that can be used to construct Skolem sequences is called a Skolem set. The existence question of deciding which sets of the form are Skolem sets was solved by Skolem [On certain distributions of integers in pairs with given differences, Math. Scand. 5 (1957) 57–68] in 1957. Many generalizations of Skolem sequences have been studied. In this paper we prove that the existence question for generalized multi-Skolem sequences is -complete. This can be seen as an upper bound on how far the generalizations of Skolem sequences can be taken while still hoping to resolve the existence question. [Copyright &y& Elsevier]

Abstract: Given an integer and any graph , the sequence graph is the graph whose set of vertices is the set of all walks of length in . Moreover, two vertices of are joined by an edge if and only if their corresponding walks are adjacent in . In this paper we prove sufficient conditions for a sequence graph to be maximally edge-connected and edge-superconnected depending on the parity of and on the vertex-connectivity of the original graph . [Copyright &y& Elsevier]

Abstract: In this paper, we are going to study some additional relations between the Stirling matrix and the Pascal matrix . Also the representation for the matrix and in terms of and will be considered. Consequently, this will give an answer to an open problem proposed by EI-Mikkawy [On a connection between the Pascal, Vandermonde and Stirling matrices—II, Appl. Math. Comput. 146 (2003) 759–769]. [Copyright &y& Elsevier]

Abstract: A shortest path connecting two vertices and is called a - geodesic. The distance between and in a graph G, denoted by , is the number of edges in a - geodesic. A graph G with n vertices is panconnected if, for each pair of vertices and for each integer k with , there is a path of length k in G that connects and . A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices , every - geodesic lies on every cycle of length k satisfying . In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs. [Copyright &y& Elsevier]

Abstract: For improving reliability of communication in communication networks, where edges are subject to failure, Kishimoto [Reliable flow with failures in a network, IEEE Trans. Reliability, 46 (1997) 308–315] defined a -reliable flow, for a given source-sink pair of nodes, in a network for , where no edge carries a flow more than a fraction of the total flow in the network, and proved a max-flow min-cut theorem with cut-capacites defined suitably. Kishimoto and Takeuchi in [A method for obtaining -reliable flow in a network, IECCE Fundamentals E-81A (1998) 776–783] provided an efficient algorithm for finding such a flow. When is an integer, say , Kishimoto and Takeuchi [On -route flows in a network, IEICE Trans. J-76-A (1993) 1185–1200 (in Japanese)] introduced the notion of a q-path flow. Kishimoto [A method for obtaining the maximum multi-route flows in a network, Networks 27 (1996) 279–291] proved a max-flow min-cut theorem for q-path flow between a given source-sink pair () of nodes and provided a strongly polynomial algorithm for finding a q-path flow from s to t of maximum flow-value. In this paper, we extend the concept of q-path flow to any real number . When q is fractional, we show that this general q-path flow can be viewed as a sum of some -path flow and some -path flow. We discuss several applications of this results, which include a simpler proof and generalization of a known result on wavelength division multiplexing problem. Finally we present a strongly polynomial, combinatorial algorithm for synthesizing an undirected network with minimum sum of edge capacities that satisfies (non-simultaneously) specified minimum requirements of q-path flow-values between all pairs of nodes, for a given real number . [Copyright &y& Elsevier]

Abstract: In the test suite generation (TSG) problem for software systems, is a set of n input parameters where each has data values, and is a collection of subsets of where the interactions of the parameters in each are thought to affect the outcome of the system. A test case for is an n-tuple that specifies the value of each input parameter in . The goal is to generate a smallest-sized test suite (i.e., a set of test cases) that covers all combinations of each . The decision version of TSG is known to be NP-complete. In this paper, we present new families of for which optimal test suites can be constructed efficiently. They differ from the ones already known by the way we characterize and . We then use these instances to generate test suites for arbitrary software systems. When each has , the sizes of the test suite are guaranteed to be at most , matching the current best bound for this problem. Our constructions utilize the structure of and ; consequently, the less “complex” and are, the better are the bounds on the sizes of the test suites. [Copyright &y& Elsevier]

Abstract: In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any , we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be . Other related investigations are also given. [Copyright &y& Elsevier]