The synchronic distance is a fundamental concept in a Petri net. Marked graphs form a subclass of Petri nets. Given a matrix D, we are interested in the problem of finding a marked graph whose synchronic distance matrix is D. It is wellknown that the synchronic disrance matrix of a marked graph is a distance matrix. In this letter, we give a matrix D such that D is a distance matrix and there does not exist a marked graph whose synchronic distance matrix is D.

In a multihop network, radio packets are often relayed through inter-mediate stations (repeaters) in order to transfer a radio packet from a source to its destination. We consider a scheduling problem in a multihop network using a graphtheoretical model. Let D=(V,A) be the digraph with a vertex set V and an arc set A. Let f be a labeling of positive integers on the arcs of A. The value of f(u,v) means a frequency band assigned on the link from u to v. We call f antitransitive if f(u,v)f(v,w) for any adjacent arcs (u,v) and (v,w) of D. The minimum antitransitive-labeling problem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NP-hard, and we propose a simple distributed approximation algorithm for it.

Dynamic Channel Assignment (DCA), which improves the efficiency of channel use in cellular mobile communication systems, requires finding an available channel for a new call after the call origination. This causes the delay which is defined as the time elapsing between call origination and completion of the channel search. For system planning, it is important to evaluate the delay characteristic of DCA because the delay corresponds to the waiting time of a call and influences service quality. It is, however, difficult to theoretically analyze the delay characteristics except its worst case behavior. The time delay of DCA has not been theoretically analyzed. The objective of this paper is analyzing the distribution and the mean value of the delay theoretically. The theoretical techniques in this paper are based on the techniques for analyzing the blocking rate performance of DCA.

The lower-bounded p-collection problem is the problem where to locate p sinks in a flow network with lower bounds such that the value of a maximum flow is maximum. This paper discusses the cover problems corresponding to the lower bounded p-collection problem. We consider the complexity of the cover problem, and we show polynomial time algorithms for its subproblems in a network with tree structure.

In a cellular system for mobile communications, every service area is divided into a number of cells for utilizing the frequency spectrum efficiently. Service areas for such systems are two dimensional, however, the analysis of the characteristics of the communication traffic for the areas are quite complicated, since the motion of the vehicles in the area can not be predicted precisely. For making the analysis easily, the areas are assumed to be band-shaped like a highway. Furthermore, in the analysis, the traffic offered to a cell is assumed to be stationary. In actual systems, the density of vehicles and the offered communication traffic is not stationary, so that many differences exist between the analysis and the actual systems. This paper presents an analysis method using state equations. The equations represent the transient characteristics of mobile communication traffic when a band-shaped service area is assumed. The transition is made by accidents or congestion, and causes the rapid offered traffic change in a communication system. In the method, numerical analysis is made under the consideration of "handoff" operation. The operation consists of surrendering the channel used in the previous cell and reassigning a new channel when the vehicle crosses the cell boundary. The analytical results are compared with the simulations, and the two results show good agreement. The method presented in this paper can be used for designing the switching system when the offered traffic changes rapidly due to accidents or congestion.

A novel algorithm, as an advanced Hybrid Channel Assignment strategy, for channel assignment problem in a cellular system is proposed. A difference from the conventional Hybrid Channel Assignment method is that flexible fixed channel allocations which are variable through the channel assignment can be performed in order to cope with varying traffic. This strategy utilizes the Channel Rearrangement technique using the artificial neural network algorithm in order to enhance channel occupancy on the fixed channels. The strategy is applied to two simulation models which are the spatial homogeneous and inhomogeneous systems in traffic. The simulation results show that the strategy can effectively improve blocking probability in comparison with pure dynamic channel assignment strategy only with the Channel Rearrangement.

In a cellular mobile system, assigning a channel for a call in a cell so as to achieve high spectral efficiency is an important problem. In usual channel assignment for a cellular mobile system, a channel can be simultaneously assigned to some cells with a constant separation distance. This usual model of a cellular mobile system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, a new channel assignment scheme has been proposed. This scheme takes the degree of interference into consideration. In the scheme, a channel is simultaneously assigned if the CIR (carrier-to-interference ratio) is more than the desired value. In this paper, we formulate this new model using a network and a new coloring problem of networks. The new coloring problem of networks is a generalization of the usual coloring problem of graphs. One of the merits of this formulation is that the degree of cochannel interference between cells can be represented. In the usual formulation using a graph, the degree of cochannel interference between cells can not be represented. Therefore, spectral efficiency in the formulation using a network is higher than spectral efficiency in the formulation using a graph. In this paper, we show that the new coloring problem is an NP-hard problem. Subsequently, we rewrite the new coloring problem of networks to a coloring problem of graphs on some assumptions and consider the relation between the results on the new coloring and the results on the usual coloring.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. However, few studies treat location problems on networks from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. This paper concerns location problems, called covering problems on flow networks. We define two types of covering problems on flow networks. We show that covering problems on undirected flow networks and a covering problem on directed flow networks are solved in polynomial times.

In mobile communication systems using Dynamic Channel Assignment, channels are possible to be rearranged so that blocking probability can be made low. The smaller the number of cells where channels are rearranged, the smaller the load on the base stations in the cells. Also, we can reduce the deterioration of communication quality caused by reassingning a new channel to a call instead of the channel already assigned. In this paper, we consider not only how to rearrange channels but also which channel should be rearranged and assigned to a new call in rearrangement, and propose very simple but effective methods for rearrangement. The ways to select a candidate channel to be rearranged and assigned to a new call in the new methods make the number of cells where a channel is rearranged smaller. We also examine the relations between characteristics and the number of cells where a channel is rearranged. Using computer simulation results, the properties of the new rearrangement methods are compared with those of the traditional methods.

Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S 2).Next we consider the d2-transmission number sequence so that the distance function is defined by a special convex function.

Recently, the mulitihop wireless network system attracts the interest of many people as a communication network system of the next generation. The multihop wireless network has unique features in which neither base stations nor wired backbone networks are required and a terminal can communicate with the other terminal beyond the transmission range by multihopping. In this network, a communication link between two terminals which can communicate directly is required a channel. Since cochannel interference may occur, we need to assign channels to communication links carefully. In this paper, we describe a channel assignment strategy which takes the degree of cochannel interference into consideration, and we evaluate an effectiveness of this strategy by computer simulations. We show that this strategy is more effective than a strategy which does not take the degree of cochannel interference into consideration. And we also consider a few channel assignment algorithms briefly.

Multimedia mobile communication systems with high-speed radio transmission supported by asynchronous transfer mode (ATM) technologies have been intensively studied over the last few years. Smaller radio zones termed microcells and picocells will be used in this kind of mobile communication systems for the purpose of high-speed radio transmission. When the coverage of a radio zone is smaller, the amount of traffic per radio zone is relatively low. It is not possible to use the cable circuits connecting the switch and base stations in an efficient manner because of the lack of the scale effect of traffic. With smaller radio zones, moreover, handoff occurs frequently as a mobile station moves. The switch is required a large capacity to handle the processing of frequent handoffs. This paper proposes a mobile network architecture controlled by the concentrated grouping of base stations. A special feature of this configuration is the ability of the network's switches to efficiently accommodate numerous base stations that control small radio zones. It can also lighten the handoff control load of switches; the effect of handoff frequency reduction is evaluated with computer simulation.

We introduce the distance between two edges in a graph (nondirected graph) as the minimum number of edges in a tieset with the two edges. Using the distance between edges we define the eccentricity ετ (ej) of an edge ej. A finite nonempty set J of positive integers (no repetitions) is an eccentric set if there exists a graph G with edge set E such that ετ (ej) J for all ei E and each positive integer in J is ετ (ej) for some ej E. In this paper, we give necessary and sufficient conditions for a set J to be eccentric.

The concept of wireless ad hoc networking has unique features in which neither base stations nor wired backbone networks are required and a mobile node can communicate with a partner beyond the transmission range by multihopping. In this paper, innovations and issues in ad hoc network technologies are reviewed. The concept of a general-purpose ad hoc network is identified as a step toward next-generation ad hoc network development. The concept of an open community network is then presented as a vision for general-purpose ad hoc networks. An open community network is a novel information infrastructure for local communities based on wireless multihopping technologies, which may support an advanced information-oriented society in the twenty-first century. As a case study, an experimental system using PHS (Personal Handy Phone System) is described and some research issues for developing an open community network are identified.

This paper discusses the teletraffic characteristics of cellular systems using Dynamic Channel Assignment. In general, it is difficult to exactly and theoretically analyze the teletraffic characteristics of Dynamic Channel Assignment. Also, it is not easy to theoretically evaluate influence of mobility on the traffic characteristics. This paper proposes approximate techniques to analyze teletraffic characteristics of Dynamic Channel Assignment considering mobility. The proposed techniques are based on Clique Packing approximation.

Wireless network systems introducing both of the cellular concept and the ad-hoc concept have been proposed. Communication between two nodes in a cell is guaranteed by relaying capability of the base station in these systems. Additionally, two nodes can directly communicate with each other while they are close to each other. We call this type of network a two-hop wireless network. The teletraffic performance of this network depends on various parameters such as the size of a cell, location of nodes, the communication range of nodes, channel assignment schemes, teletraffic behavior and so on. The purpose of this paper is to theoretically analyze the teletraffic performance of the network, which has been evaluated by computer simulation, by introducing a simple model. This paper shows a technique to analyze the performance in this model. Also, this paper considers the range in which the two-hop wireless network works well for the efficient use of channels.

This paper describes communication traffic characteristics in cellular systems employing the concept of reuse partitioning and Dynamic Channel Assignment. Such systems hava a problem of the spatial unbalance of blocking probability. The objective of this paper is overcoming this problem. To accomplish this objective, we use a method for analyzing communication traffic characteristics. We also show results on traffic characteristics in the systems.

The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree3 in a network, is bound to some constant K0.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.

In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.