摘要:

AbstractA graphGis called invertible if its adjacency matrixAhas an inverse which is the adjacency matrix of some graphH.All such graphs were shown by Harary and Minc to have the formnK2. We now introduce signed invertible (or briefly s‐invertible) graphsGas those whose inverseHis a signed graph. We identify two infinite classes of s‐invertible graphs: the pathsP2nof even order, and the corona of any graph with K1. We then characterize s‐invertible

ISSN:0028-3045    

DOI:10.1002/net.3230180302

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

年代:1988

数据来源: WILEY

摘要:

AbstractThe tolerance approach to sensitivity analysis, in contrast to classical sensitivity analysis, allows for simultaneous and independent perturbations of objective function coefficients and of right‐hand‐side terms from their original values. Here we specialize this approach to network problems. The specialization yields streamlined results in that the computations can be performed directly on a netw

ISSN:0028-3045    

DOI:10.1002/net.3230180303

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

年代:1988

数据来源: WILEY

摘要:

AbstractAdominating setin a graphGis a set of verticesDsuch that every vertex ofGis either inDor is adjacent some vertex ofD.Thedomination numberΓ(G) ofGis the minimum cardinality of any dominating set. A graph isvertex domination‐criticalif the removal of any vertex decreases its domination number. This paper gives examples and properties of vertex domination‐critical graphs, presents a method of constructing them, and poses some open questions. In the process several results for arbitrary graphs are prese

ISSN:0028-3045    

DOI:10.1002/net.3230180304

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

年代:1988

数据来源: WILEY

摘要:

AbstractThe Capacitated Arc Routing Problem (CARP), a generalization of the arc routing problems such as the Chinese Postman Problem (CPP), is a very practical distribution management problem which has many real‐world applications. This paper briefly reviews two existing lower bounding procedures—the Matching Lower Bound and the Node Scanning Lower Bound, then introduces a new bounding technique to provide tighter lower bounds on the problem soluti

ISSN:0028-3045    

DOI:10.1002/net.3230180305

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

年代:1988

数据来源: WILEY

摘要:

AbstractThis paper considers Stochastic Shortest Path (SSP) problems in probabilistic networks. A variety of approaches have already been proposed in the literature. However, unlike in the deterministic case, they are related to distinct models, interpretations and applications. We have chosen to look at the case where detours from the original path must be taken whenever the “first‐choice” arc fails. The main results obtained include the proof of some counterintuitive facts (e.g., the SSP may contain a cycle), the proof of the validity of applying stochastic programming to this problem and the proof that the computational complexity of a particular SSP problem is polyn

ISSN:0028-3045    

DOI:10.1002/net.3230180306

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

年代:1988

数据来源: WILEY

摘要:

AbstractThis paper describes an efficient way to test theVAP‐free(Vertex Accumulation Point free) planarity of one‐ and two‐dimensionaldynamic graphs. Dynamic graphsare infinite graphs consisting of an infinite number of basic cells connected regularly according to labels in a finite graph called astatic graph.Dynamic graphs arize in the design of highly regular VLSI circuits, such as systolic arrays and digital signal processing chips. We show that VAP‐free planarity testing of dynamic graphs can be done efficiently by making use of their regularity. First, we will establish necessary conditions for VAP‐free planarity of dynamic graphs. Then we show the existence of a small finite graph which is planar if and only if the original dynamic graph is VAP‐free planar. From this it follows that VAP‐free planarity testing of one‐ and two‐dimensional dynamic graphs is asymptomically no more difficult than planarity testing of finite graphs, and thus can be do

ISSN:0028-3045    

DOI:10.1002/net.3230180307

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

年代:1988

数据来源: WILEY

摘要:

AbstractThe scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.

ISSN:0028-3045    

DOI:10.1002/net.3230180308

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

年代:1988

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230180309

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

年代:1988

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230180310

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

年代:1988

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230180311

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

年代:1988

数据来源: WILEY