Computer Engineering Commons^™

Complexity Of Some Geometric Problems, Marcus Schaefer

Technical Reports

We show that recognizing intersection graphs of convex sets has the same complexity as deciding truth in the existential first-order theory of the reals. Comparing this to similar results on the rectilinear crossing number and intersection graphs of line segments, we argue that there is a need to recognize this level of complexity as its own class.

Global Verification And Analysis Of Network Access Control Configuration, Ehab Al-Shaer, Will Marrero, Adel El-Atawy, Khalid Elbadawi

Technical Reports

Network devices such as routers, firewalls, IPSec gateways, and NAT are configured using access control lists. However, recent studies and ISP surveys show that the management of access control configurations is a highly complex and error prone task. Without automated global configuration management tools, unreachablility and insecurity problems due to the misconfiguration of network devices become an ever more likely.

In this report, we present a novel approach that models the global end-to-end behavior of access control devices in the network including routers, firewalls, NAT, IPSec gateways for unicast and multicast packets. Our model represents the network as a state …

Computing The K-Hop Neighborhoods In Wireless Networks Locally, Iyad A. Kanj, Andreas Wiese, Fenghui Zhang

Technical Reports

A k-local distributed algorithm (k is a natural number) is a distributed algorithm in which the computation at every point/device in the distributed system modeled as a graph depends solely on the initial states of the points that are at most k hops away from the point. A distributed algorithm is local if it is k-local for some fixed natural number k. Local distributed algorithms are very important, especially for applications in ad-hoc sensor and wireless networks, since such algorithms are naturally scalable, robust, and fault tolerant. Clearly, an essential component of any k-local distributed algorithm is computing the k-hop …

On The Pseudo-Achromatic Number Problem, Jianer Chen, Iyad A. Kanj, Jie Meng, Gei Xia, Fenghui Zhang

Technical Reports

We study the parameterized complexity of the pseudo-achromatic number problem: Given an undirected graph and a parameter k, determine if the graph can be partitioned into k groups such that every two groups are connected by at least one edge. This problem has been extensively studied in graph theory and combinatorial optimization. We show that the problem has a kernel of at most (k-2)(k+1) vertices that is constructable in time O(m\sqrt{n}), where n and m are the number of vertices and edges, respectively, in the graph, and k is the parameter. This directly implies that the problem is fixed-parameter tractable. …

Preliminary Results With A Targeted Online Java Course, Amber Settle, Will Marrero, Chad Settle

Technical Reports

While the College of Computing and Digital Media has offered online courses for 7 years, courses targeted specifically at online students remain in the minority. In this report, we investigate both student learning and student satisfaction with a targeted online introductory Java course developed by the first co-author. Initial results show that this targeted course has equivalent outcomes with respect to student learning and strongly improved student satisfaction.

Independent Study On Infinite Graph Theory, Martin Zimmermann

Technical Reports

In this paper we will prove some results about infinite graphs. We show that for every linear order there is a graph with a distinguished vertex such that the edges adjacent to that vertex have the given order in any plane drawing. The other results are concerned with connectivity. We prove a generalization of a characterization of 2-­connected graphs and prove that k-­connectedness does not imply the existence of finite k­connected subgraphs for k > 2.

Strong Hanani-Tutte On The Projective Plane, Michael J. Pelsmajer, Marcus Schaefer, Despina Stasi

Technical Reports

If a graph can be drawn in the projective plane so that every two non-adjacent edges cross an even number of times, then the graph can be embedded in the projective plane.

Clustering And Its Application In Requirements Engineering, Chuan Duan

Technical Reports

Large scale software systems challenge almost every activity in the software development life-cycle, including tasks related to eliciting, analyzing, and specifying requirements. Fortunately many of these complexities can be addressed through clustering the requirements in order to create abstractions that are meaningful to human stakeholders. For example, the requirements elicitation process can be supported through dynamically clustering incoming stakeholders’ requests into themes. Cross-cutting concerns, which have a significant impact on the architectural design, can be identified through the use of fuzzy clustering techniques and metrics designed to detect when a theme cross-cuts the dominant decomposition of the system. Finally, traceability …

Computing Lightweight Spanning Subgraphs Locally, Iyad A. Kanj, Ljubomir Perkovic, Ge Xia

Technical Reports

We consider the problem of computing bounded-degree lightweight plane spanning subgraphs of unit disk graphs in the local distributed model of computation. We are motivated by the hypothesis that such subgraphs can provide the underlying network topology for efficient unicasting and/or multicasting in wireless distributed systems. We start by showing that, for any integer $k \geq 2$, there exists a $k$-local distributed algorithm that, given a unit disk graph $U$ embedded in the plane, constructs a plane subgraph of $U$ containing a Euclidean Minimum Spanning Tree (EMST) of $V(U)$, whose degree is at most 6, and whose total weight is …