The Sylvester graph and Moore graphs

The combinatorial structure of a famous graph with large girth, namely the Sylvester graph, is studied. Simple techniques, such as two-way counting, partitions, circuit chasing and covers are used to identify smaller structures and to show that there are no other graphs that share a small number of regularity properties with it. As a consequence, we show the same for the Hoffman–Singleton graph. We notice that some much larger graphs with large girth have similar properties, and could be studied using the same techniques. In particular, we show that just as the Hoffman–Singleton graph contains the Sylvester graph, a Moore graph of valency 57, whose existence is a famous open problem, must contain a subgraph with a structure that is similar to the one we derived for the Sylvester graph.     

A graph theoretical approach for the yield enhancement of reconfigurable VLSI/WSI arrays

In this paper, we consider the yield enhancement of programmable structures by logical restructuring of the circuit placement. In this approach, an initial placement of a circuit on the array is first obtained by simulated annealing on a defect-free array. To implement the circuit on a defective array, the initial placement is reconfigured so that only the defect-free portion of the array is used. Customizing a given initial placement for each defective chip by logical restructuring, if done very fast, would be a cost effective method for yield enhancement. We describe a formulation of the circuit reconfiguration problem in terms of graphs and pebbles, wherein each processing element (PE) of the array is represented by a vertex which is classified as either defective or nondefective, depending upon whether the PE that it represents is defective or nondefective. Vertices representing PEs that are physically adjacent are connected by an edge, whose length is a measure of the proximity of the PEs. The logic elements of a circuit are represented by weighted pebbles. The initial placement of the circuit on the array corresponds to an initial placement of the pebbles on the vertices of the graph, with at most one pebble per vertex. The problem is to successively shift these pebbles along paths in the graph, such that after reconfiguration no pebble is located on a defective vertex, and an associated cost function is minimized. We describe four cost measures using weighted displacement and weighted shift of the pebbles. After presenting exact algorithms for some special cases of the problem, we prove the NP-completeness of the general cases of the corresponding decision problems.     

Minimization of circuit registers: Retiming revisited

We address the following problem: given a synchronous digital circuit, is it possible to construct a new circuit computing the same function as the original one but using a minimal number of registers? We show that the minimal number of registers is the size of the minimal cut on a bi-infinite graph, namely the unfolding of the dependencies in the digital circuit. Furthermore, the construction of such a cut and the corresponding circuit can be done in polynomial time, using a max-flow min-cut result of Orlin for one-periodic bi-infinite graphs. Finally, we show the relation between this construction and the retiming technique introduced by Leiserson and Saxe.     

Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

Consider the traveling salesman problem (TSP) defined on the complete graph, where the edge costs satisfy the triangle inequality. Let TOUR denote the optimal solution value for the TSP. Two well-known relaxations of the TSP are the subtour elimination problem and the 2-matching problem. If we let SUBT and 2M represent the optimal solution values for these two relaxations, then it has been conjectured that TOUR/SUBT ≤4/3, and that 2M/SUBT ≤10/9.In this paper, we exploit the structure of certain 1/2-integer solutions for the subtour elimination problem in order to obtain low cost TSP and 2-matching solutions. In particular, we show that for cost functions for which the optimal subtour elimination solution found falls into our classes, the above two conjectures are true. Our proofs are constructive and could be implemented in polynomial time, and thus, for such cost functions, provide a 4/3 (or better) approximation algorithm for the TSP.     

A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees

Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme.     

On external-memory MST, SSSP and multi-way planar graph separation

Recently external memory graph problems have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open.The results in this paper fall in two main classes. First we develop an improved algorithm for the problem of computing a minimum spanning tree (MST) of a general undirected graph. Second we show that on planar undirected graphs the problems of computing a multi-way graph separation and single source shortest paths (SSSP) can be reduced I/O-efficiently to planar breadth-first search (BFS). Since BFS can be trivially reduced to SSSP by assigning all edges weight one, it follows that in external memory planar BFS, SSSP, and multi-way separation are equivalent. That is, if any of these problems can be solved I/O-efficiently, then all of them can be solved I/O-efficiently in the same bound. Our planar graph results have subsequently been used to obtain I/O-efficient algorithms for all fundamental problems on planar undirected graphs.     

基于时变需求的集成多级供应链生产订货策略研究

考虑一个时变需求环境下集成多级供应链问题,在有限的规划时间内销售商以固定周期订货,而生产商以不同的周期生产,目的是寻找销售商最优的订货周期和生产商最佳的生产策略,从而使供应链系统的总运营成本最少.建立了该问题的混合整数非线性规划模型,求解该模型分为两步：先求对应一个订货周期的最佳生产策略,再求最优的订货周期,第一步用到了图论里求最短路方法.给出了两个步骤的算法和程序,实验证明它们是有效的.通过算例对模型进行了分析,研究了各参数对最优解及最小费用的影响.     

On competitive sequential location in a network with a decreasing demand intensity

We introduce and analyze a Hotelling like game wherein players can locate in a city, at a fixed cost, according to an exogenously given order. Demand intensity is assumed to be strictly decreasing in distance and players locate in the city as long as it is profitable for them to do so. For a linear city (i) we explicitly determine the number of players who will locate in equilibrium, (ii) we fully characterize and compute the unique family of equilibrium locations, and (iii) we show that players’ equilibrium expected profits decline in their position in the order. Our results are then extended to a city represented by an undirected weighted graph whose edge lengths are not too small and co-location on nodes of the graph is not permitted. Further, we compare the equilibrium outcomes with the optimal policy of a monopolist who faces an identical problem and who needs to decide upon the number of stores to open and their locations in the city so as to maximize total profit.     

Minimum Eulerian circuits and minimum de Bruijn sequences

Given a digraph (directed graph) with a labeling on its arcs, we study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label.     

Domain decomposition methods with graph cuts algorithms for total variation minimization

Recently, graph cuts algorithms have been used to solve variational image restoration problems, especially for noise removal and segmentation. Compared to time-marching PDE methods, graph cuts based methods are more efficient and able to obtain the global minimizer. However, for high resolution and large-scale images, the cost of both memory and computational time increases dramatically. In this paper, we combine the domain decomposition method and the graph cuts algorithm for solving the total variation minimizations with L ¹ and L ² fidelity term. Numerous numerical experiments on large-scale data demonstrate the proposed algorithm yield good results in terms of computational time and memory usage.     

Linear arrangement problems on recursively partitioned graphs

We analyze the complexity of the restrictions of linear arrangement problems that are obtained if the legal permutations of the nodes are restricted to those that can be obtained by orderings of a binary tree structuring the nodes of the graph, the so-called p-tree. These versions of the linear arrangement problems occur in several places in current circuit layout systems. There the p-tree is the result of a recursive partitioning process of the graph. We show that the MINCUT LINEAR ARRANGEMENT problem and the OPTIMAL LINEAR ARRANGEMENT problem can be solved in polynomial time, if the p-tree is balanced. All other versions of the linear arrangement problems we analyzed are NP-complete.     

Induced Circuits in Planar Graphs

In McDiarmid, B. Reed, A. Schrijver, and B. Shepherd (Univ. of Waterloo Tech. Rep., 1990) a polynomial-time algorithm is given for the problem of finding a minimum cost circuit without chords (induced circuit) traversing two given vertices of a planar graph. The algorithm is based on the ellipsoid method. Here we give an O(n²) combinatorial algorithm to determine whether two nodes in a planar graph lie on an induced circuit. We also give a min-max relation for the problem of finding a maximum number of paths connecting two given vertices in a planar graph so that each pair of these paths forms an induced circuit.     

近三角剖分图的均衡二重少圈覆盖

近三角剖分图是一连通平面图，其内面均为三角形而其外面可能不是．令Ｇ为一具有ｎ个节点的近三角剖分图，Ｃ为 Ｇ的一个小圈二重覆盖（ＳＣＤＣ）^［２］．令(?)则Ｃ₀。称为Ｇ的均衡小圈二重覆盖．本文将证明：若Ｇ为外平面图，则 δ（Ｃ₀）≤ ２；否则δ（Ｃ₀）≤４。     

On-line secret sharing

In a perfect secret sharing scheme the dealer distributes shares to participants so that qualified subsets can recover the secret, while unqualified subsets have no information on the secret. In an on-line secret sharing scheme the dealer assigns shares in the order the participants show up, knowing only those qualified subsets whose all members she has seen. We often assume that the overall access structure (the set of minimal qualified subsets) is known and only the order of the participants is unknown. On-line secret sharing is a useful primitive when the set of participants grows in time, and redistributing the secret when a new participant shows up is too expensive. In this paper we start the investigation of unconditionally secure on-line secret sharing schemes. The complexity of a secret sharing scheme is the size of the largest share a single participant can receive over the size of the secret. The infimum of this amount in the on-line or off-line setting is the on-line or off-line complexity of the access structure, respectively. For paths on at most five vertices and cycles on at most six vertices the on-line and offline complexities are equal, while for other paths and cycles these values differ. We show that the gap between these values can be arbitrarily large even for graph based access structures. We present a general on-line secret sharing scheme that we call first-fit. Its complexity is the maximal degree of the access structure. We show, however, that this on-line scheme is never optimal: the on-line complexity is always strictly less than the maximal degree. On the other hand, we give examples where the first-fit scheme is almost optimal, namely, the on-line complexity can be arbitrarily close to the maximal degree. The performance ratio is the ratio of the on-line and off-line complexities of the same access structure. We show that for graphs the performance ratio is smaller than the number of vertices, and for an infinite family of graphs the performance ratio is at least constant times the square root of the number of vertices.     

On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery problem in this class is determined by a connected graph, a cost function defined on its edges and a special chosen vertex in that graph which will be referred to as the post office. It is assumed that the edges in the graph are owned by different individuals and the delivery game is concerned with the allocation of the traveling costs incurred by the server, who starts at the post office and is expected to traverse all edges in the graph before returning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respectively) if for each delivery problem in which G is the underlying graph the associated delivery game is submodular (totally balanced, balanced, respectively). For undirected graphs we prove that CP-submodular graphs and CP-totally balanced graphs are weakly cyclic graphs and conversely. An undirected graph is shown to be CP-balanced if and only if it is a weakly Euler graph. For directed graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submodular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs can be recognized in linear time. Received May 20, 1997 / Revised version received August 18, 1998?Published online June 11, 1999     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

Approximating connected facility location with buy-at-bulk edge costs via random sampling

In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of infinite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suffice to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.     

Competitive Algorithms for Relaxed List Update and Multilevel Caching

We study relaxed list update problem (RLUP), in which access requests are made to items stored in a list. The cost to access the jth item x_j is c_j, where c_i ≤ c_{i + 1} for all i. After the access, x_j can be repeatedly swapped, at no cost, with any item that precedes it in the list. This problem was introduced by Aggarwal et al. (1987, “Proc. 19th Symp. Theory of Computing,” pp. 305–313) as a model for the management of hierarchical memory that consists of a number of caches of increasing size and access time. They also proved that a version of LRU is C-competitive, for some C, for a restricted class of cost functions. We give an efficient offline algorithm that computes the optimal strategy for RLUP. We also show an elegant characterization of work functions for RLUP. We prove that move-to-front (MTF) is optimally competitive for RLUP with any cost function. An interesting feature of the proof is that it does not involve any estimates on the competitive ratio. Finally, we give a lower bound on the competitive ratio of online algorithms for RLUP.     

Oriented bipartite graphs and the Goldbach graph

In this paper, we study oriented bipartite graphs. In particular, we introduce “bitransitive” graphs. Several characterizations of bitransitive bitournaments are obtained. We show that bitransitive bitounaments are equivalent to acyclic bitournaments. As applications, we characterize acyclic bitournaments with Hamiltonian paths, determine the number of non-isomorphic acyclic bitournaments of a given order, and solve the graph-isomorphism problem in linear time for acyclic bitournaments. Next, we prove the well-known Caccetta-Häggkvist Conjecture for oriented bipartite graphs in some cases for which it is unsolved, in general, for oriented graphs. We also introduce the concept of undirected as well as oriented “odd-even” graphs. We characterize bipartite graphs and acyclic oriented bipartite graphs in terms of them. In fact, we show that any bipartite graph (acyclic oriented bipartite graph) can be represented by some odd-even graph (oriented odd-even graph). We obtain some conditions for connectedness of odd-even graphs. This study of odd-even graphs and their connectedness is motivated by a special family of odd-even graphs which we call “Goldbach graphs”. We show that the famous Goldbach's conjecture is equivalent to the connectedness of Goldbach graphs. Several other number theoretic conjectures (e.g., the twin prime conjecture) are related to various parameters of Goldbach graphs, motivating us to study the nature of vertex-degrees and independent sets of these graphs. Finally, we observe Hamiltonian properties of some odd-even graphs related to Goldbach graphs for a small number of vertices.     

Integrated scheduling and batch ordering for construction project

Multi-Mode Resource Constrained Project Scheduling Problem and material batch ordering for construction project are integrated to help project manager consider various trade-offs among several costs, such as renewable resources’ cost, material price, ordering cost, back-ordering cost, inventory holding cost and reward/penalty for early/late project completion. Therefore, we prove a mixed integer programming model and impel to calculate inventory holding cost and back order cost in objective function. Moreover, a hybrid algorithm combined adapted harmony search and genetic algorithm is proposed correspondingly. In order to inherit elitist solution and maintain population’s diversity simultaneously, we add a selection operator when the harmony memory is initialized and modify the replacement operator based on distance. Besides, genetic algorithm is adopted based on a ‘012’ coding scheme. Finally, algorithm and model performance is presented and several project instances are provided with different network structures and realizations to discuss the factors on total cost.