Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 10 of 10 for “"special graph classes"”.
-
Rainbow Colorings in Graphs
In this thesis, we deal with rainbow colorings of graphs. We engage not with the rainbow connection number but with counting of rainbow colorings in graphs with k colors. We introduce the rainbow polynomial and prove some results for some special graph classes. Furthermore, we obtain bounds for the …
-
Προσεγγιστικά σχήματα, κλίκες, χρώματα και πυκνότεροι υπογράφοι
… we study the problem of finding the densest k-subgraph of a given graph G = (V, E). We present algorithms of polynomial time as well as approximation results on special graph classes. Analytically, in the thesis we study polynomial time algorithms for the densest k-subgraph problem on weighted …
-
Domination in graphs with application to network reliability
… we investigate different domination-related graph polynomials, like the connected domination polynomial, the independent domination polynomial, and the total domination polynomial. We prove some basic properties of these polynomials and obtain formulas for the calculation in special graph …
-
Analysis and Optimization of Communication Networks with Flow Requirements
… covers the connectivity of the surviving graph together with some minimum bandwidth. We study essential and irrelevant edges for those reliability measures. Further, we study a splitting approach to transform the reliability of the graph into the probability that subgraphs have a certain …
-
Computing and Bounding the Scattering Number of Graphs
In this thesis we study the scattering number of graphs, a parameter introduced by Jung in 1978, from two different perspectives. First, we investigate it under a computational lens, proving that the scattering number of bipartite and planar graphs cannot be computed in polynomial time unless P=NP, …
-
Graph-theoretic Properties of Control Flow Graphs and Applications
… appropriate width parameters of control flow graphs so that certain computationally hard problems of practical interest become efficiently solvable. A well-known result of Thorup states that the treewidth of control flow graphs arising from structured (goto-free) programs is at most six. …
-
Network Bargaining: Creating Stability Using Blocking Sets
… Solution to answer this question for the special case of two agents. Kleinberg and Tardos extended this idea to network games, and introduced a model they call the Bargaining Game. They search for surplus divisions with a notion of fairness, defined as balanced solutions, that follow the …
-
Scheduling in computer and communication systems and generalized graph coloring problems
… with weighted generalizations of the classical graph coloring problems motivated by scheduling arising in computer and communication systems. The most general problems we attack are called bounded max-vertex/edge-coloring problems and take as input a vertex/edge weighted graph and a bound b. In …
-
Routing and Stabbing
ROUTING. Let G be a simple, connected, undirected graph. We consider routing with preprocessing in G. In a preprocessing step, each vertex of G receives a label and a routing table. Then, we must be able to route a packet between any two vertices s and t of G, where each step may use only the label …
-
Geometric Graphs: Reachability, Long Trees and Short Cycles
Given a set S of n point sites, a geometric graph is a graph with S as its vertex set whose edges are drawn as line segments connecting the sites. The edges that are present between these sites can be defined by geometric properties of the site set. When talking about weighted edges, the weight of …