Algorithms for the constrained maximum-weight connected graph problem

Given a positive integer R and a weight for each vertex in a graph, the maximum-weight connected graph (MCG) problem is to find a connected subgraph with R vertices that maximizes the sum of the weights. The MCG problem is strongly NP-complete, and we study a special case of it: the constrained MCG (CMCG) problem, which is the MCG problem with a constraint of having a predetermined vertex included in the solution. We first show that the Steiner tree problem is a special case of the CMCG problem. Then we present three optimization algorithms for the CMCG problem. The first two algorithms deal with special graphs (tree and layered graphs) and employ different dynamic programming techniques, solving the CMCG problem in polynomial times. The third one deals with a general graph and uses a variant of the Balas additive method with an imbedded connectivity test and a pruning method. We also present a heuristic algorithm for the CMCG problem with a general graph and its bound analysis. We combine the two algorithms, heuristic and optimization, and present a practical solution method to the CMCG problem. Computational results are reported and future research issues are discussed. © 1996 John Wiley & Sons, Inc.     

A search game on the union of graphs with immobile hider

We consider a search game for an immobile hider on one arc of the union of n graphs joined at one or two points. We evaluate a lower bound on the value of a strategy for the hider on this union. When we have identical graphs, we give the conditions under which the value of the strategy for the hider on this union is greater than or equal to n times the value of this strategy on one graph. We also solve search games on graphs, consisting of an odd number of arcs, each of length one, joining two points. © 1995 John Wiley & Sons, Inc.     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Decomposition algorithms for the maximum-weight connected graph problem

Given a positive integer R and a weight for each vertex in a graph, the maximum-weight connected graph problem (MCG) is to find a connected subgraph with R vertices that maximizes the sum of their weights. MCG has applications to communication network design and facility expansion. The constrained MCG (CMCG) is MCG with a constraint that one predetermined vertex must be included in the solution. In this paper, we introduce a class of decomposition algorithms for MCG. These algorithms decompose MCG into a number of small CMCGs by adding vertices one at a time and building a partial graph. They differ in the ordering of adding vertices. Proving that finding an ordering that gives the minimum number of CMCGs is NP-complete, we present three heuristic algorithms. Experimental results show that these heuristics are very effective in reducing computation and that different orderings can significantly affect the number of CMCGs to be solved. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 817–837, 1998     

A vertex-closing approach to the p-center problem

This article uses a vertex-closing approach to investigate the p-center problem. The optimal set of vertices to close are found in imbedded subgraphs of the original graph. Properties of these subgraphs are presented and then used to characterize the optimal solution, to establish a priori upper and lower bounds, to establish refined lower bounds, and to verify the optimality of solutions. These subgraphs form the foundation of two polynomial algorithms of complexity O(|E| log |E|) and O(|E|²). The algorithms are proven to converge to an optimum for special cases, and computational evidence is provided which suggests that they produce very good solutions more generally. Both algorithms perform very well on problems where p is large relative to the number of vertices n, specifically, when p/n ≥ 0.30. One of the algorithms is especially efficient for solving a sequence of problems on the same graph.     

On locally optimal independent sets and vertex covers

In this paper, we introduce a new notion of local optimality and demonstrate its application to the problem of finding optimal independent sets and vertex covers in k-claw free graphs. The maximum independent set problem in k-claw free graphs has interesting applications in the design of electronic testing fixtures for printed circuit boards [13]. For this problem, our concept of local optimality enabled us to devise an efficient heuristic algorithm which outperforms the currently best approximation algorithm by nearly a factor of two in terms of worst case bound. We believe that the idea of local optimality suggested in this paper can also be applied to other combinatorial problems such as the clique problem, the dominating set problem and the graph coloring problem. © 1996 John Wiley & Sons, Inc.     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Weighted vertex packing problem for specially structured geometric graphs

Consider a set of vertices V = {1, 2,…, n} placed on a two-dimensional Euclidean plane R² with each vertex attached a nonnegative weight w: V → R. For a given constant d>0, the geometric graph G = (V, E) is defined to have edge set E = {(i, j): d_ij ⩽ d} with d_ij being the Euclidean distance between vertices i and j. The geometric vertex packing (GVP) problem, which is often called the independent set problem, is defined as selecting the set of pairwise nonadjacent vertices with maximum total weight. We limit our attention to the special case that no vertex is within a distance βd of any other vertices where 0 ⩽ β < 1. A special value of β (= 1/2) is referred to frequently because of its correspondence to a manufacturing problem in circuit board testing. In this article we show that the weighted vertex packing problem for the specially structured geometric graph (SGVP) defined with the above restriction is NP-complete even for the case that all vertex weights are unity and for any β. Polynomial procedures have been designed for generating cuts to obtain tight LP upper bounds for the SGVP. Two heuristics with bounded worst-case performance are applied to the LP solution to produce a feasible solution and a lower bound. We then use a branch-and-bound procedure to solve the problem to optimality. Computational results on large-scale SGVP problems will be discussed. © 1995 John Wiley & Sons, Inc.     

A graph theoretic interpretation of the sufficiency conditions for the contiguous-binary-switching (CBS)-rule

A sufficient condition for the optimality of the CBS-rule due to W. Smith is given a graphic interpretation in terms of ‘convex’ graphs. A convex graph is uniquely constructed (except for a homomorphism), and has the property that the optimum is achieved from any starting point.     

Machine sequencing: Disjunctive graphs and degree-constrained subgraphs

In two earlier papers, we proposed algorithms for finding an optimal sequence of processing m items on q machines, by finding a minimaximal path in a disjunctive network. In a third paper, this latter model was generalized (from 2-state to 3-state disjunctive graphs) so as to accommodate project scheduling with resource constraints. In this paper, we discuss another algorithm for the (2-state) disjunctive network problem, closely related to those mentioned above. To make the paper self-contained, section 2 briefly describes the problem. Section 3 introduces a class of constraints which forms the basis of the algorithm discussed in section 4. The constraints have only 1, ?1, or 0 as coefficients on the left-hand side, integers on the right-hand side. The whole procedure of generating these constraints and finding a feasible solution whenever a new constraint is added, can be interpreted (section 5) as a process of generating a graph with degree-constraints on its nodes, and then finding a subgraph satisfying the degree-constraints. The nodes of the graph are generated by solving a critical-path-problem, the feasible subgraphs are found by implicit enumeration.     

A fast infiltration game on n arcs

Starting from a safe base, an Infiltrator tries to reach a sensitive zone within a given time limit without being detected by a Guard. The Infiltrator can move with speed at most u, while the Guard can only perform a restricted number of searches. A discrete variant of this zero-sum game played on a graph consisting of two vertices joined by n nonintersecting arcs is investigated. Optimal strategies and an explicit expression for its value are obtained. © 1996 John Wiley & Sons, Inc.     

Nonpreemptive scheduling of independent tasks with prespecified processor allocations

In this article we study the problem of scheduling independent tasks, each of which requires the simultaneous availability of a set of prespecified processors, with the objective of minimizing the maximum completion time. We propose a graph-theoretical approach and identify a class of polynomial instances, corresponding to comparability graphs. We show that the scheduling problem is polynomially equivalent to the problem of extending a graph to a comparability graph whose maximum weighted clique has minimum weight. Using this formulation we show that in some cases it is possible to decompose the problem according to the canonical decomposition of the graph. Finally, a general solution procedure is given that includes a branch-and-bound algorithm for the solution of subproblems which can be neither decomposed nor solved in polynomial time. Some examples and computational results are presented. © 1994 John Wiley & Sons, Inc.     

A computation procedure for the exact solution of location-allocation problems with rectangular distances

A method is presented to locate and allocate p new facilities in relation to n existing facilities. Each of the n existing facilities has a requirement flow which must be supplied by the new facilities. Rectangular distances are assumed to exist between all facilities. The algorithm proceeds in two stages. In the first stage a set of all possible optimal new facility locations is determined by a set reduction algorithm. The resultant problem is shown to be equivalent to finding the p-median of a weighted connected graph. In the second stage the optimal locations and allocations are obtained by using a technique for solving the p-median problem.     

Initial point search on weighted trees

An initial point search game on a weighted graph involves a searcher who wants to minimize search and travel costs seeking a hider who wants to maximize these costs. The searcher starts from a specified vertex 0 and searches each vertex in some order. The hider chooses a nonzero vertex and remains there. We solve the game in which the graph is a simple tree, and use this solution to solve a search game on a tree in which each branch is itself a weighted graph with a certain property, and the searcher is obliged to search the entire branch before departing. © 1994 John Wiley & Sons, Inc.     

Optimal interdiction policy for a flow network

This paper analyzes the problem faced by a field commander who, confronted by an enemy on N battlefields, must determine an interdiction policy for the enemy's logistics system which minimizes the amount of war material flowing through this system per unit time. The resource utilized to achieve this interdiction is subject to constraint. It can be shown that this problem is equivalent to determining the set of arcs Z* to remove subject to constraint from a directed graph G such that the resulting maximal flow is minimized. A branch and bound algorithm for the solution to this problem is described, and a numerical example is provided.     

Continuous sampling plans for markov-dependent production processes

This article discusses the behavior of three continuous sampling plans: continuous sampling plan 1 (CSP 1) and continuous sampling plan 2 (CSP 2) developed by Dodge [5] and Dodge and Torrey [7], and multilevel continuous sampling plan 2 (MLP 2) developed by Lieberman and Solomon [11], when the quality of successive units in a continuous production process follows a two-state time-homogeneous Markov chain. We first derive the average outgoing quality (AOQ) expressions of these plans. Exact procedures for determining the average outgoing quality limit (AOQL) can be obtained only for CSP 1. For CSP 2 and MLP 2 plans, iterative procedures have been used to obtain the AOQL contours. For these plans, it is assumed that the serial correlation coefficient between the two consecutive random variables of the Markov chain is known. In addition, estimation procedures for the coefficient are given. We show that if the serial correlation coefficient of the Markov chain is positive (negative), the AOQL is increased (decreased) as compared to the case when the successive units in the production process follows a Bernoulli pattern. Let r denote the number of production units examined in succession which are found to be of good quality and k denote the inverse of the sampling fraction employed when quality is good. Then if r and k are sufficiently small, it is observed from the graph that, for small departures of the serial correlation coefficient from zero, the AOQL values do not differ significantly for each of the three plans; whereas for sufficiently large values of r and k, the AOQL values differ significantly. Various aspects of these plans, such as their operating characteristics 2 (OC 2) and the serial correlation coefficient, are discussed.     

面向图计算应用的处理器访存通路优化设计与实现

针对图计算应用的访存特点,提出并实现一种支持高并发、乱序和异步访存的高并发访存模块(High Concurrency and high Performance Fetcher, HCPF)。通过软-硬件协同的设计方法,HCPF可同时处理192条共8种类型的内存访问请求,且访存粒度可由用户定义,满足图计算应用对海量低延迟细粒度数据访问的需求。同时,HCPF扩展了基于内存语义的跨计算节点定制互连技术,支持远程内存的细粒度直接访问,为后续实现分布式图计算框架提供技术基础。结合上述两个核心研究内容,基于流水线RISC-V处理器核,设计并实现了可支持HCPF的RISC-V片上系统(System-on-Chip,SoC)架构,搭建基于FPGA的原型验证平台,并使用自研测试程序对HCPF进行初步性能评测。实验结果表明,HCPF相比原有访存通路,最高可将基于数组和随机地址的两种随机内存访问性能分别提升至3.5倍和2.7倍。远程内存直接访问4 Byte数据的延时仅为1.63μs。     

On labeling the vertices of products of complete graphs with distance constraints

Variations of Hale's channel assignment problem, the L(j, k)‐labeling problem and the radio labeling problem require the assignment of integers to the vertices of a graph G subject to various distance constraints. The λ_j,k‐number of G and the radio number of G are respectively the minimum span among all L(j, k)‐labelings, and the minimum span plus 1 of all radio labelings of G (defined in the Introduction). In this paper, we establish the λ_j,k‐number of ∏ K for pairwise relatively prime integers t₁ < t₂ < … < t_q, t₁ ≥ 2. We also show the existence of an infinite class of graphs G with radio number |V(G)| for any diameter d(G). © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

利用交互依赖活动集对C4ISR系统进行重组

一个复杂的C4ISR系统由若干子系统组成,子系统之间的交互依赖关系应该尽量少.利用活动模型构造系统的活动邻接矩阵,用图论中的路径矩阵来识别强连通子图,从而得出交互依赖活动集.具有交互依赖关系的活动尽量安排在一个子系统内部.利用这种方法来对C4ISR系统进行重组.