摘要:

AbstractA graphGisvertex domination‐criticalif for any vertexvofGthe domination number ofG‐vis less than the domination number ofG. If such a graphGhas domination number γ, it is called γ‐critical. Brigham et al. studied γ‐critical graphs and posed the following questions: (1) IfGis a γ‐critical graph, is |V| ≥ (δ + 1)(γ ‐ 1) + 1?(2) If a γ‐critical graphGhas (Δ + 1)(γ ‐ 1) + 1 vertices, isGregular? (3) Doesi = γfor all γ‐critical graphs? (4) Letdbe the diameter of the γ‐critical graphG. Doesd≤ 2(γ ‐ 1) always hold? We show that the first and third questions have a negative answer

ISSN:0028-3045    

DOI:10.1002/net.3230250203

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

年代:1995

数据来源: WILEY

摘要:

AbstractSuppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location‐routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O(nlogn) or O(n). Multiserver variants of the problem on a tree are proved to be NP‐complete. Some modifications of the problem are also investiga

ISSN:0028-3045    

DOI:10.1002/net.3230250204

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

年代:1995

数据来源: WILEY

摘要:

AbstractUnit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP‐hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on‐line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular obje

ISSN:0028-3045    

DOI:10.1002/net.3230250205

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

年代:1995

数据来源: WILEY

摘要:

AbstractGiven a set of terminals in the plane, a rectilinear Steiner minimal tree is a shortest interconnection among these terminals using only horizontal and vertical edges. We present an algorithm that constructs a rectilinear Steiner minimal tree for any input terminal set. On a workstation, problems involving 20 input terminals can be solved in a few seconds, and problems involving 30 input terminals can be solved, on average, in 30 min. Previous algorithms could only solve 16‐ or 17‐point point problems within the 30 min time bound. Problems involving 35 points can be solved, on average, within a day. Our experiments were run on uniformly distributed data on an integer g

ISSN:0028-3045    

DOI:10.1002/net.3230250206

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe constrained maximum flow problem is to send the maximum possible flow from a source node s to a sink node t in a directed network subject to a budget constraint that the cost of flow is no more thanD. In this paper, we consider two versions of this problem: (i) when the cost of flow on each arc is a linear function of the amount of flow, and (ii) when the cost of flow is a convex function of the amount of flow. We suggest capacity scaling algorithms that solve both versions of the constrained maximum flow problem in O((m log M) S(n, m)) time, wherenis the number of nodes in the network;m, the number of arcs; M, an upper bound on the largest element in the data: and S(n, m), the time required to solve a shortest path problem with nonnegative arc lengths. Our algorithms are generalizations of the capacity scaling algorithms for the minimum cost flow and convex cost flow problems and illustrate the power of capacity scaling algorithms to solve variants of the minimum cost flow problem in polynomial time.

ISSN:0028-3045    

DOI:10.1002/net.3230250207

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

年代:1995

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230250202

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

年代:1995

数据来源: WILEY