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 20 of 23 for “"Conflict graph"”.
-
Examining a subproblem of the frequency assignment problem using a conflict graph
… once a frequency assignment is found. Given a conflict graph for a communications network, the problem involves finding the maximum number of arcs in the corresponding digraph. This digraph is a worst case model for the actual network and will show which additional links may be added to the …
-
Implementation of an efficient algorithm to detect maximal cliques in a conflict graph
… the frequency allocation. In this thesis, graphs are used to model radio communications networks. The problem considered is the detection of maximal cliques, representing subnets, from the graph model. However, detection of cliques is an NP-complete problem. Since NP-complete problems are …
-
Interference Management in Dense 802.11 Networks
… video. This dissertation presents a practical conflict-graph (CG) based approach to designing self-organizing enterprise wireless networks (or WLANs) where interference is centrally managed by the network infrastructure. The key idea is to use potential interference information (available in …
-
A graph theoretic approach to the optimal slot utilization problem for naval communication networks
… on a particular frequency as vertices in a graph, and the relationships between them as edges in that graph. We then analyze the structure of the resultant graph and find an upper bound on the chromatic number of its conflict graph to take into account all possible patterns of interference …
-
Visibility analysis of landmark-based navigation
… art gallery problem in which the visibility graph of the landmarks is required to be connected. The chromatic art gallery problem can be phrased in terms of a landmark placement problem combined with a graph coloring problem. The landmarks are placed such that each point in the polygon is …
-
A study of university timetabling that blends graph coloring with the satisfaction of various essential and preferential conditions
Constructing a satisfactory conflict-free semester-long timetable of courses and creating a similarly satisfactory conflict-free timetable for end-of-semester final examinations are two closely related and often difficult problems that colleges and universities face each semester. We discuss the …
-
MAC layer resource allocation algorithms for OFDM/TDMA wireless networks
… are studied based on frameworks developed from Graph Theory and Game Theory. Centralized and distributed resource location algorithms based on graph theory are introduced that assign both time-slots and channels to wireless transmission links in multihop networks. For finding the possible set of …
-
Solving a mixed-integer programming formulation of a classification model with misclassification limits
… matrix. Methods for generating edges of the conflict graph and conflict hypergraphs are discussed. The conflict graph is employed for finding cuts in a branch-and-bound framework. This technique and others lead to improvement in solution time over industry-standard software on instances …
-
Evolution of the Secondary Spectrum Market
… primary needs to select an independent set in a conflict graph and the price at each location. We consider two scenarios--i) the number of locations is small, and ii) the number of locations is large. We show that when the number of locations is small, in a symmetric NE strategy, each primary …
-
Maximizing throughput while maintaining fairness and priority in wireless ad-hoc networks
… In our model we represented these inter nodal conflicts using 'Conflict Graph or Conflict Matrix' and presented scheduling schemes to address issues like network throughput, fairness and QoS (priority) in a network. We particularly studied the transmission patterns in a network given a specific …
-
Spectrum Requirements for Interference-Free Wireless Mesh Networks
… computationally simple method of building the conflict graph based on signal-to-interference ratio model with shadowing is developed.Computationally simple and effective new heuristics are developed to find channel assignments from the conflict graph for the extended coloring problem with …
-
ΠΡΟΒΛΗΜΑΤΑ ΣΥΝΤΟΝΙΣΜΟΥ ΤΑΥΤΟΧΡΟΝΩΝ ΠΡΟΣΠΕΛΑΣΕΩΝ ΣΕ ΒΑΣΕΙΣ ΔΕΔΟΜΕΝΩΝ
… OF MULTIVERSION SERIALIZABILITY (MVSR) BASED ON CONFLICTS (MVCSR) AND DISCUSS ITS RELATION WITH THE WELL KNOWN SINGLE VERSION CONFLICT SERIALIZABILITY (CSR). WE PROVE THAT IT IS NP-COMPLETE TO DECIDE WHETHER A SET OF SCHEDULES IS ON-LINE SCHEDULABLE (OLS). WE INTRODUCE THE CONCEPT OF MAXIMAL OLS …
-
Solving structured 0/1 integer programs arising from truck dispatching scheduling problems
… polytope is obtained. In addition, a notion of "conflict graph" is introduced and utilized to obtain an approximating node-packing polytope for the convex hull of all 0/1 solutions. The branch-and-cut solver generates cuts based on both the knapsack constraints and the approximating node-packing …
-
Effective Provisioning in Multi-Interface Multi-Channel Wireless Mesh Networks
… To assess interference among links, we use a conflict graph for all channels of the three technologies. Furthermore, we formulate a joint interference-aware routing, Interface Assignment (IA), and Channel Assignment (CA) scheme using Integer Linear Programming (ILP) for both static and dynamic …
-
Collaborative mobile services
… buyers, which is characterized by a complex conflict graph. We evaluate DA² and demonstrate its superior performance via simulations on conflict graphs generated with real cell tower locations.
-
Joint scheduling and power control for predictable per-packet reliability and real-time guarantee in URLLC
… algorithm exploits one-hop information in the conflict graph and incorporates optimal real-time scheduling principles to address the challenges of distributed multi-cell, multi-channel PPRC scheduling. Overall, this work bridges the gap between theoretical reliability guarantees and practical …
-
Resource constrained shortest paths and extensions
… cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice and often appears as a subproblem in many decomposition schemes for difficult optimization problems. We begin with a study of the …
-
Capture, analysis and synthesis of photorealistic crowds
… of crowds have been well-studied in computer graphics, the resulting control rig sequences require a laborious model-based graphics pipeline to render photorealistic videos of crowds. Over the past ten years, data-driven techniques for rendering imagery of complex phenomena have become a …
-
Radio Resource Management for Wireless Mesh Networks Supporting Heterogeneous Traffic
… results show that, compared to a conventional conflict-graph approach, our proposed approach effectively fosters frequency reuse, thereby improving system performance; Secondly, we propose three approaches for joint power-frequency-time resource allocation. Simulation results show that all of …
-
Optimizing performance and energy efficiency of group communication and internet of things in cognitive radio networks
… The network is modeled using a multi-layer hyper graph, and the secondary users' transmission is scheduled after establishing the conflict graph. Due to the difficulty of solving the problem optimally, a modified version of an Ant Colony meta-heuristic algorithm is employed to solve the problem. …
Page 1 of 2