9333297
A two-zone hybrid routing protocol for mobile ad hoc networks
Recently, an elegant routing protocol, the zone routing protocol (ZRP), was proposed to provide a hybrid routing framework that is locally proactive and globally reactive, with the goal of minimizing the sum of the proactive and reactive control overhead. The key idea of ZRP is that each node proactively advertises its link state over a fixed number of hops, called the zone radius. These local advertisements provide each node with an updated view of its routing zone - the collection of all nodes and links that are reachable within the zone radius. The nodes on the boundary of the routing zone are called peripheral nodes and play an important role in the reactive zone-based route discovery. The main contribution of this work is to propose a novel hybrid routing protocol - the two-zone routing protocol (TZRP) - as a nontrivial extension of ZRP. In contrast with the original ZRP where a single zone serves a dual purpose, TZRP aims to decouple the protocol's ability to adapt to traffic characteristics from its ability to adapt to mobility. In support of this goal, in TZRP each node maintains two zones: a crisp zone and a fuzzy zone. By adjusting the sizes of these two zones independently, a lower total routing control overhead can be achieved. Extensive simulation results show that TZRP is a general MANET routing framework that can balance the trade offs between various routing control overheads more effectively than ZRP in a wide range of network conditions.
7945895
Wireless sensor networks: leveraging the virtual infrastructure
Overlaying a virtual infrastructure over a physical network is a time-honored strategy for conquering scale. We design a general-purpose virtual architecture for wireless sensor networks and show that it can be leveraged by a number of different protocols.
2805859
A time-optimal solution for the path cover problem on cographs
We show that the notoriously difficult problem of finding and reporting the smallest number of vertex-disjoint paths that cover the vertices of a graph can be solved time- and work-optimally for cographs. Our result implies that for this class of graphs the task of finding a Hamiltonian path can be solved time- and work-optimally in parallel.It was open for more than 10 years to find a time- and work-optimal parallel solution for this important problem. Our contribution is to offer an optimal solution to this important problem. We begin by showing that any algorithm that solves an instance of size n of the problem must take ?(logn) time on the CREW, even if an infinite number of processors are available. We then go on to show that this time lower bound is tight by devising an EREW algorithm that, given an n-vertex cograph G represented by its cotree, finds and reports all the paths in a minimum path cover in O(logn) time using n/logn processors.
5533650
The hierarchical cliques interconnection network
The fully connected network possesses extremely good topological, fault-tolerant, and embedding properties. However, due to its high degree, the fully connected network has not been an attractive candidate for building parallel computers. On the other hand, tree-based networks are popular as parallel computer networks, even though they suffer from poor fault-tolerance and embedding properties. The hierarchical cliques interconnection network described in this paper incorporates positive features of the fully connected network and the tree network. In other words, the hierarchical cliques possess such desirable properties as low diameter, low degree, self routing, versatile embedding, good fault-tolerance and strong resilience. Hierarchical cliques can efficiently embed most important networks and possess a scalable, modular structure. Further, by combining hierarchical cliques with fat trees congestion in the upper levels can be alleviated.
932666
Q-Win – A New Admission and Handoff Management Scheme for Multimedia LEO Satellite Networks
Low Earth Orbit (LEO) satellite networks are deployed as an enhancement to terrestrial wireless networks in order to provide broadband services to users regardless of their location. In addition to global coverage, these satellite systems support communications with hand-held devices and offer low cost-per-minute access cost, making them promising platform for Personal Communication Services (PCS). LEO satellites are expected to support multimedia traffic and to provide their users with the negotiated Quality of Service (QoS). However, the limited bandwidth of the satellite channel, satellite rotation around the Earth and mobility of end-users makes QoS provisioning and mobility management a challenging task. One important mobility problem is the intra-satellite handoff management. The main contribution of this work is to propose Q-Win, a novel call admission and handoff management scheme for LEO satellite networks. A key ingredient in our scheme is a companion predictive bandwidth allocation strategy that exploits the topology of the network and contributes to maintaining high bandwidth utilization. Our bandwidth allocation scheme is specifically tailored to meet the QoS needs of multimedia connections. The performance of Q-Win is compared to that of two recent schemes proposed in the literature. Simulation results show that our scheme offers low call dropping probability, providing for reliable handoff of on-going calls, good call blocking probability for new call requests, while maintaining bandwidth utilization high.
5840834
Asteroidal Triple-Free Graphs
Many families of perfect graphs such as interval graphs, permutation graphs, trapezoid graphs and cocomparability graphs demonstrate a type of linear ordering of their vertex sets. These graphs are all subfamilies of a class of graphs called the asteroidal triple-free graphs. (An independent triple {x, y, z} is called an asteroidal triple (AT, for short) if between any pair in the triple there exists a path that avoids the neighbourhood of the third vertex.) In this paper we argue that the property of being AT-free is what is enforcing the linear ordering of the vertex sets. To justify this claim, we present various structural properties and characterizations of AT-free graphs.
39112817
Asteroidal Triple-Free Graphs
An independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third is called an asteroidal triple. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triples. The motivation for this investigation was provided, in part, by the fact that the AT-free graphs provide a common generalization of interval, permutation, trapezoid, and cocomparability graphs. The main contribution of this work is to investigate and reveal fundamental structural properties of AT-free graphs. Specifically, we show that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. We then provide characterizations of AT-free graphs in terms of dominating pairs and minimal triangulations. Subsequently, we state and prove a decomposition theorem for AT-free graphs. An assortment of other properties of AT-free graphs is also provided. These properties generalize known structural properties of interval, permutation, trapezoid, and cocomparability graphs.
29579371
A New Characterization of Unbreakable Graphs
A nonempty set C of vertices of a graph G is a star-cutset if G\C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. A graph G is unbreakable if neither G nor its complement Ḡ contains a star-cutset. In this note we present a new characterization of unbreakable graphs.
11691370
Efficient algorithms for graphs with few P4's
Abstract We show that a large variety of NP-complete problems can be solved efficiently for graphs with ‘few’ P 4 's. We consider domination problems (domination, total domination, independent domination, connected domination and dominating clique), the Steiner tree problem, the vertex ranking problem, the pathwidth problem, the path cover number problem, the hamiltonian circuit problem, the list coloring problem and the precoloring extension problem. We show that all these problems can be solved in linear time for the class of ( q , q −4)-graphs, for every fixed q . These are graphs for which no set of at most q vertices induces more than q −4 different P 4 's.
205023063
A new conjecture about minimal imperfect graphs
Abstract H. Meyniel proved that in every minimal imperfect graph, every pair of vertices is joined by a chordless path containing an odd number of edges. We conjectured that in every minimal imperfect graph, every pair of vertices is joined by a path containing an even number of edges. We give an equivalent version of this new conjecture.