A steganographer network corresponds to a graphic structure that the involved vertices (or called nodes) denote social entities such as the data encoders and data decoders, and the associated edges represent any real communicable channels or other social links that could be utilized for steganography. Unlike traditional steganographic algorithms, a steganographer network models steganographic communication by an abstract way such that the concerned underlying characteristics of steganography are quantized as analyzable parameters in the network. In this paper, we will analyze two problems in a steganographer network. The first problem is a passive attack to a steganographer network where a network monitor has collected a list of suspicious vertices corresponding to the data encoders or decoders. The network monitor expects to break (disconnect) the steganographic communication down between the suspicious vertices while keeping the cost as low as possible. The second one relates to determining a set of vertices corresponding to the data encoders (senders) such that all vertices can share a message by neighbors. We point that, the two problems are equivalent to the minimum cut problem and the minimum-weight dominating set problem.
The authors in @cite_6 have pointed that Eq. (2) is equivalent to solving the Steiner Tree Problem (STP) problem @cite_16 , which is NP-hard. The STP is seen as a generalization of two other combinatorial optimization problems, i.e., the shortest path problem and the minimum spanning tree (MST) problem. If the STP deals with only two terminals, it reduces to finding a shortest path. If all vertices are terminals, it is equivalent to the MST problem. Therefore, one may employ the existing approximation algorithms designed for the STP to find the suitable strategy for steganographic communication.
@cite_16 @cite_6
1968004989 2975802624 75217549 2069002708
Given a set of input points, the Steiner Tree Problem (STP) is to find a minimum-length tree that connects the input points, where it is possible to add new points to minimize the length of the tree. Solving the STP is of great importance since it is one of the fundamental problems in network design, very large scale integration routing, multicast routing, wire length estimation, computational biology, and many other areas. However, the STP is NP-hard, which shatters any hopes of finding a polynomial-time algorithm to solve the problem exactly. This is why the majority of research has looked at finding efficient heuristic algorithms. Additionally, many authors focused their work on utilizing the ever-increasing computational power and developed many parallel and distributed methods for solving the problem. In this way we are able to obtain better results in less time than ever before. Here, we present a survey of the parallel and distributed methods for solving the STP and discuss some of their applications. We study variations of Steiner tree problem. Let P = p1, p2, ...,p n be a set of n terminals in the Euclidean plane. For a positive integer k, the bottleneck Steiner tree problem (BSTP for short) is to find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. For a positive constant R, the Steiner tree problem with minimum number of Steiner points (STP - MSP for short) asks for a Steiner tree such that each edge in the tree has length at most R and the number of Steiner points is minimized. In this paper, we give (1) a ratio-√3 + e approximation algorithm for BSTP, where e is an arbitrary positive number; (2) a ratio-3 approximation algorithm for STP-MSP with running time O(n 3 ); (3) a ratio-5 2 approximation algorithm for STP-MSP. We consider the Steiner tree problem in graphs under uncertainty, the so-called two-stage stochastic Steiner tree problem (SSTP). The problem consists of two stages: In the first stage, we do not know which nodes need to be connected. Instead, we know costs at which we may buy edges, and a set of possible scenarios one of which will arise in the second stage. Each scenario consists of its own terminal set, a probability, and second-stage edge costs. We want to find a selection of first-stage edges and second-stage edges for each scenario that minimizes the expected costs and satisfies all connectivity requirements. We show that SSTP is in the class of fixed-parameter tractable problems (FPT), parameterized by the number of terminals. Additionally, we transfer our results to the directed and the prize-collecting variant of SSTP. Abstract In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STPMSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5.