摘要:

AbstractAn algorithm is developed for the selection of a cycle basis of a graph which corresponds to a highly sparse cycle adjacency matrix, hence providing an efficient means for the mesh analysis of networks. Unlike the existing methods, this algorithm reduces the overlaps of the cycles instead of their lengths. The results are compared with those of the previous methods through some examples. The cycles are also ordered to obtain banded cycle adjacency matrices.

ISSN:0028-3045    

DOI:10.1002/net.3230190302

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractAnexact cutin a source‐sink network is a set of arcs which interesects each source‐sink path in exactly one arc. This paper investigates the problem of finding a maximum weight exact cut in a network. The problem is shown to be polynomially equivalent to that of determining the relevant arcs (arcs on at least one source‐sink path) in the network and is NP‐hard for general directed networks. There are, however, several important classes of network—including undirected networks—for which polynominal time algorithms do exist to solve the maximum weight exact

ISSN:0028-3045    

DOI:10.1002/net.3230190303

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractThis article addresses a problem that comes up frequently in network design, and routing. A source is to distribute flows to nodes in the network. Sending flow along an arc involves a fixed cost for using the arc and a variable cost for each ujnit of flow. We show tht the problem of finding a minimum cost collection of arcs along which flows will be directed is an NP‐hard problem. We describe a procedure of solving the problem to optimality and several heuristics. In particular, we conclude that the use of polynomially derived Lagrange multipliers yields good quality solutions and bounds and can be implemented in a distributed processing mode in the networ

ISSN:0028-3045    

DOI:10.1002/net.3230190304

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper is intended as a survey in the area of network synthesis and optimum network design, which, in view of the importance and variety of the underlying applications, has attraced, since the early 1960s, much interest in the Operations Research community. Indeed, if the first models were studied in connection with telecommunication networks, the range of applications kept on getting broader and broader, including transportation networks, computer and teleprocessing networks, energy transport systems, water distribution networks, etc. However, beyond the apparent diversity of practical situations involved, most of these applications can be accounted for (modulo possibly a few minor adaptations), by a rather limited number of basic models. One of the main purposes of this paper is to provide the reader with a relevant classification of the area which will help him identify the fundamental structure of the problem (if any) he has to cope with, and relate it to already published work. In order to obtain a fairly good coverage of the matter, we have thus been led to identify three basic models aroung which the whole paper is organized: a general model using minimum cost multicommodity flows (Section 2); models in terms of tree‐like networks (Section 3); models using nonsmultaneous single‐commodity or multicommodity flows (Section 4). In each bcase the most important variants of the basic models have been surveyed with the purpose of providing as much information as possible concerning (a) the various contexts of applications from which the problem arose; (b) the main computational methods proposed in the literature for solving it, with emphasis on those techniques which appear at present, to be most efficient or promis

ISSN:0028-3045    

DOI:10.1002/net.3230190305

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractConsider a “sea” ofMsquares which contains (at some unknown location) a “battleship” ofKsquares. Both the sea and the battleship can assume any rectangular shape. Our goal is to find the battleship by probing at least one of its squares. In this paper we describe adeterministicstrategy for this problem which is guaranteed to locate the battleship in at mostc1M/Kprobes, wherec1

ISSN:0028-3045    

DOI:10.1002/net.3230190306

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

摘要:

AbstractA maximum independent set of a graph is a set of vertices with maximum cardinality such that no pair of vertices is connected by an edge. Choukhmane and Franco have presented a polynomial time approximation algorithm for the maximum independent set problem in cubic planar graphs. IfMis taken as the ratio of the size of the independent set produced by their algorithm to the size of a maximum independent set of the input graph, then they show that their algorithm givesM⩾ 6/7 for any cubic planar graph andM⩾ 7/8 for a triangle‐free cubic planar graph. We give a new, stronger proof of thier result. The new proof shows that their algorithm actually givesM⩾ 7/8 for all cubic planar

ISSN:0028-3045    

DOI:10.1002/net.3230190307

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230190308

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1989

数据来源: WILEY