In this paper, we consider interference networks where the connectivity is known globally while the channel gains are known up to a particular distance from each node. In this setting, we provide a new achievability, called Maximal Clique Scheduling (MCS), which is a special case of Maximal Independent Graph Scheduling (MIG Scheduling) proposed earlier. The strategy is evaluated using the notion of normalized sum rate which is a metric to evaluate performance of networks with mismatched knowledge. The achievable normalized sum rate of the proposed MCS strategy is easier to analyze for certain classes of networks and can be used to bound the normalized sum rate of MIG Scheduling. We investigate the normalized sum rate achieved by MCS for two classes of networks. The first class is formed by interference networks where each link is connected with probability $p$. The second class is derived from Wyner 1-D model of placements of base stations and mobile nodes. We find that increasing knowledge about the network leads to increasing normalized sum-rate. However, in a random network, the increase is slower as compared to Wyner network because most nodes are far away from a node and hence learning more helps less until the whole network is known.

Zugl.: Habil.-Schr.

Zugl.: Berlin, Techn. Univ., Diss., 2005 u.d.T.: Borrmann, Stefan: Wissenschaftlich begründete Leitlinien für die Praxis sozialer Arbeit

Zugl.: Konstanz, Univ., Diss., 2008

The search for max-cliques in graphs is a well established NP-complete problem in graph theory and algorithm design, with many algorithms designed to make use of internal structures of specific types of graphs. We study the extension of the problem of searching for max-cliques in graphs to hypergraphs with constant edge size k, and adapt existing algorithms for graphs to work in k-hypergraphs. In particular, we are interested in the generalization of circulant graphs to circulant k-hypergraphs, and provide a definition of this type of hypergraph. We design and implement a new algorithm to perform max-clique searches on circulant k-hypergraphs. This algorithm combines ideas from a Russian doll algorithm for max-cliques in graphs (Ostergard 2002) with an algorithm based on necklaces for a class of circulant k-hypergraphs (Tzanakis, Moura, Stevens and Panario 2016). We examine the performance of our new algorithm against a set of adapted algorithms (backtracking and Russian doll search for general k-hypergraphs, and necklace-based search for circulant k-hypergraphs) in a set of benchmarking experiments across various densities and edge sizes. This study reveals that the new algorithm outperforms the others when edge density of the hypergraph is high, and that the pure necklace-based algorithm is best in the case of low densities. Finally, we use our new algorithm to perform an exhaustive search on circulant 4-hypergraphs constructed from linear feedback shift register sequences on finite fields of order q that yields covering arrays. The search is completed for 2 <= q <= 5 which solves the open case of q=5 left by Tzanakis et al.

Clustering applications dealing with perception based or biased data lead to models with non-disjunct clusters. There, objects to be clustered are allowed to belong to several clusters at the same time which results in a fuzzy clustering. It can be shown that this is equivalent to searching all maximal cliques in dynamic graphs like G_t=(V,E_t), where E_(t-1) in E_t, t=1,... ,T; E_0=(). In this article algorithms are provided to track all maximal cliques in a fully dynamic graph. It is naturally to raise the question about the maximum clique, having all maximal cliques. Therefore this article discusses potentials and drawbacks for this problem as well. (author's abstract) / Series: Working Papers on Information Systems, Information Business and Operations

A tree decomposition is a tool which allows for analysis of the underlying tree structure of graphs which are not trees. Given a class of graphs with bounded tree width, many NP-complete problems can be computed in linear time for graphs in the class. Clique width of a graph G is a measure of the number of labels required to construct G using several particular graph operations. For any integer k, both the class of graphs with tree width at most k and the class of graphs with clique width at most k have a decidable monadic second order theory. In this paper we explore some recent results in applying these graph measures and their relation to monadic second order logic.

This dissertation considers a class of closely related NP-hard otpimization problems on graphs that arise in many important applications, including network-based data mining, analysis of the stock market, social networks, coding theory, fault diagnosis, molecular biology, biochemistry and genomics. In particular, the problems of interest include the classical maximum independent set problem (MISP) and maximum clique problem (MCP), their vertex-weighted vesrions, as well as novel optimization models that can be viewed as practical relaxations of their classical counterparts. The concept of clique has been a popular instrument in analysis of networks, and is, essentially, an idealized model of a “closely connected group”, or a cluster. But, at the same time, the restrictive nature of the definition of clique makes the clique model impractical in many applications. This motivated the development of clique relaxation models that relax different properties of a clique. On the one hand, while still possessing some clique-like properties, clique relaxations are not as “perfect” as cliques; and on the other hand, they do not exhibit the disadvantages associated with a clique. Using clique relaxations allows one to compromise between perfectness and flexibility, between ideality and reality, which is a usual issue that an engineer deals with when applying theoretical knowledge to solve practical problems in industry. The clique relaxation models studied in this dissertation were first proposed in the literature on social network analysis, however they have not been well investigated from a mathematical programming perspective. This dissertation considers new techniques for solving the MWISP and clique relaxation problems and investigates their effectiveness from theoretical and computational perspectives. The main results obtained in this work include (i) developing a scale-reduction approach for MWISP based on the concept of critical set and comparing it theoretically with other approaches; (ii) obtaining theoretical complexity results for clique relaxation problems; (iii) developing algorithms for solving the clique relaxation problems exactly; (iv) carrying out computational experiments to demonstrate the performance of the proposed approaches, and, finally, (v) applying the obtained theoretical results to several real-life problems.

Zugl.: Göttingen, Univ., Diss., 2005

Universiẗat, Diss., 2005--Göttingen.