45814647
An integrated object-oriented analysis and design method emphasizing entity/class relationship and operation finding
Abstract This paper presents an object-oriented analysis and design (OOAD) method that integrates analysis and design phases based on entity and class relationships. This method concentrates on establishing relationships between entities and between classes and on representing and refining the relationships. In describing the system's behavior, this method provides modified event trace diagrams and a textual document to capture the interactions among operations within the classes. It also provides uniform notations and specific procedures in order to identify classes, objects, attributes, and operations.
35963439
A counter-example to a clustering heuristic
2698140
On fixed-parameter tractability and approximability of NP-hard optimization problems
Fixed-parameter tractability and approximability of NP-hard optimization problems are studied based on a model GC(s(n), Pi /sub k//sup L/). The main results are (1) a class of NP-hard optimization problems, including dominating-set and zero-one integer-programing, are fixed-parameter tractable if and only if GC(s(n), Pi /sub 2//sup L/) contained in P for some s(n) in omega (log n); (2) most approximable NP-hard optimization problems are fixed-parameter tractable. In particular, the class MAX NP is fixed-parameter tractable; (3) a class of optimization problems do not have fully polynomial time approximation scheme unless GC(s(n), Pi /sub k//sup L/) contained in P for some s(n) in omega (log n) and for some k>l; and (4) every fixed-parameter tractable optimization problem can be approximated in polynomial time to a non-trivial ratio.<<ETX>>
14208339
Using Nondeterminism to Design Efficient Deterministic Algorithms
Abstract
In this paper we illustrate how nondeterminism can be used
conveniently and effectively in designing efficient deterministic
algorithms. In particular, our method gives a parameterized
algorithm of running time O((5.7 k)k n) for the 3-D matching
problem, which significantly improves the previous algorithm by
Downey et al. The algorithm can be generalized to
yield an improved algorithm for the r-D matching problem for any
positive integer r. The method can also be employed in designing
deterministic algorithms for other optimization problems as well.


40686134
Probabilistic analysis of connectivity on mesh networks
Mesh networks are among the most important network topologies in massive multiprocessor parallel systems. This paper proposes a new method for calculating the connectivity probability for mesh networks, which uses thorough mathematical methods to derive the relationship between the network node failure probability and the network connectivity probability in mesh networks. The results show that practical mesh networks can remain connected with very high probability. For example, it is formally proved that when the network node failure probability is bounded by 0.12%, the mesh networks with up to forty thousand nodes remain connected with probability larger than 99%. Our methods are also useful for deriving lower bounds on the connectivity probability for other computer networks.
5737685
Payload analysis of anonymous communication system with host-based rerouting mechanism
Host-based rerouting mechanism is a routing scheme that stores and forwards data in application layer. With this, users can communicate in a indirect way. Thus, identity information such as IP addresses can be effectively hidden against eavesdropper. In anonymous communication systems, such as mixes, onion routing, and crowds, this mechanism is adopted to provide anonymity. This mechanism, however, can result in extra overhead in performance such as communication delay and participant payload, which may affect the applications of anonymous communication systems. In this paper, we study quantitatively the participant payload induced by host-based rerouting mechanisms. A probability formula for calculating the participant payload is derived, which shows that the number of participants, the number of rerouting paths, and the probability distribution of the length of rerouting paths determine the participant payload. Applying this formula to the practical anonymous communication system, crowds, we get immediately the precise expected participant payload, which significantly improves Reiter and Rubin's original analysis and demonstrates that the participant payload in crowds remains a constant and independent of the variation of the number of participants in crowds. Simulation results are presented to testify our theoretical analysis.
42479552
A note on practical construction of maximum bandwidth paths
Constructing maximum bandwidth paths has been a basic operation in the study of network routing, in particular in the recent study of network QoS routing. In the literature, it has been proposed that a maximum bandwidth path be constructed by a modified Dijkstra's algorithm or by a modified Bellman-Ford algorithm. In this short note. we show that maximum bandwidth paths can be constructed by a modified Kruskal's algorithm. We demonstrate that this approach is simpler, easier in implementation, more flexible, and faster than the previously proposed algorithms.