摘要:

AbstractThe matching problem in bipartite graphs can be solved by an elegant primal‐dual algorithm. The purpose of this paper is to introduce concepts which make it possible to generalize this algorithm to some classes of hypergraphs. We illustrate the approach by providing a polynomial primal‐dual algorithm for the matching problem in hypergraphs without odd cyc

ISSN:0028-3045    

DOI:10.1002/net.3230170402

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

年代:1987

数据来源: WILEY

摘要:

AbstractWe establish that finding a minimum cut or a maximum flow in an acyclic network is no easier than the corresponding problem on a general network.

ISSN:0028-3045    

DOI:10.1002/net.3230170403

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

年代:1987

数据来源: 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.3230170404

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

年代:1987

数据来源: WILEY

摘要:

AbstractA method for accelerating the computational performance of branch exchange heuristics for symmetric traveling salesman problems (TSP's) is presented. The improvement in performance is obtained by considering only exchanges that have a good chance of producing a better solution. In the instance of the 3–optimal heuristic, the approach reduces the number of operations required to obtain a good solution to a TSP withNnodes fromO(N3)toO(N2), without a corresponding degradation in the quality of the solution. Most of the results are produced for Euclidean TSP's, but evidence is presented that indicates that thes results apply equally well if not more strongly to the general symmetric TS

ISSN:0028-3045    

DOI:10.1002/net.3230170405

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

年代:1987

数据来源: WILEY

摘要:

AbstractA linear placement technique that uses an objective function of the sum of wiring lengths is proposed. The method evolves from well‐known concepts in job sequencing and network flow. The relation between a job sequencing problem and this linear placement problem was demonstrated by Lawler. Also, Sidney proposed decomposition algorithms for job sequencing problems. Building on Lawler's and Sidney's work, we first develop a polynomial‐time algorithm to obtain optimal solutions for the special case of parallel graphs. Adolphson and Hu applied the max‐flow min‐cut method of the network flow problem to the partitioning of general placement problems. However, when the cut operation creates the cut of the same configuration as the previous cut operations, no additional partitioning information is obtained. We devise an optimal graph modification that tries to change the configuration of the cut for further partitioning of the problem, and achieve the maximum partitioning of the problem. Finally, a heuristic algorithm is derived to solve some Very Large Scale Integrated Circuits (VLSI) design linear placement problems. A comparison with published papers shows that our VLSI placement method produces better

ISSN:0028-3045    

DOI:10.1002/net.3230170406

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

年代:1987

数据来源: WILEY

摘要:

AbstractConsider a graph G and a positive integerk. Themaximum k‐coloringproblem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. Themaximum k‐coveringproblem is to findkdisjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximumk‐colorings and maximumk‐coverings of transitive

ISSN:0028-3045    

DOI:10.1002/net.3230170407

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

年代:1987

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230170401

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

年代:1987

数据来源: WILEY