← All Problems
P-complete

Network Simulation (NetSim)

Category: Miscellaneous

Input

A fully connected undirected network with $N$ vertices, a capacity $C(i, j)$ for each link $ij$ (counted in “trunks”), a list of tuples specifying call arrival and holding times, and a designated call $c$.

Problem

During the simulation of the network (see Greenberg, Lubachevsky, and Wang [1] for details) is call $c$ blocked?

Status

$\P$-complete (Greenberg, Lubachevsky, and Wang [1]).

Remarks

The reduction to show hardness is from MCVP. They also prove that multirate simulation, in which a call may require more than one trunk on each link on its route, is $\P$-complete even for $N$ equal to two. See TC for a related question.

References

  1. A. G. Greenberg, B. D. Lubachevsky, and L.-C. Wang (1993). Experience in massively parallel discrete event simulation.
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.12.8.

Related Problems