28567623
Edge k-to-1 Homomorphisms
35455221
A characterization of pancyclic complements of line graphs
Abstract We characterize graphs G such that the complements of their line graphs are pancyclic.
10618110
Dominating subgraphs in graphs with some forbidden structures
Abstract We characterize the triangle-free graphs with neither induced path of six vertices nor induced cycle of six vertices and the triangle-free graphs without induced path of six vertices in terms of dominating subgraphs.
10016971
Improved bottleneck domination algorithms
W.C.K. Yen introduced BOTTLENECK DOMINATION and BOTTLENECK INDEPENDENT DOMINATION. He presented an O(n log n + m)- time algorithm to compute a minimum bottleneck dominating set. He also obtained that the BOTTLENECK INDEPENDENT DOMINATING SET problem is NP-complete, even when restricted to planar graphs.We present simple linear time algorithms for the BOTTLENECK DOMINATING SET and the BOTTLENECK TOTAL DOMINATING SET problem. Furthermore, we give polynomial time algorithms (most of them with linear time-complexities) for the BOTTLENECK INDEPENDENT DOMINATING SET problem on the following graph classes: AT-free graphs, chordal graphs, split graphs, permutation graphs, graphs of bounded treewidth, and graphs of clique-width at most k with a given k-expression.
10851913
Taming heterogeneity - the Ptolemy approach
Modern embedded computing systems tend to be heterogeneous in the sense of being composed of subsystems with very different characteristics, which communicate and interact in a variety of ways-synchronous or asynchronous, buffered or unbuffered, etc. Obviously, when designing such systems, a modeling language needs to reflect this heterogeneity. Today's modeling environments usually offer a variant of what we call amorphous heterogeneity to address this problem. This paper argues that modeling systems in this manner leads to unexpected and hard-to-analyze interactions between the communication mechanisms and proposes a more structured approach to heterogeneity, called hierarchical heterogeneity, to solve this problem. It proposes a model structure and semantic framework that support this form of heterogeneity, and discusses the issues arising from heterogeneous component interaction and the desire for component reuse. It introduces the notion of domain polymorphism as a way to address these issues.
18232832
Tree-assisted gossiping for overlay video distribution
Given its readily deployable nature and broad applications for digital entertainment, video streaming through overlay networks has received much attention recently. While a tree topology is often advocated due to its scalability, it suffers from discontinuous playback under highly dynamic network environments. For on-demand streaming, the asynchronicity among client requests further aggravates the problem. On the other hand, gossip protocols using random message dissemination, though robust, fail to meet the real-time constraints for streaming applications. In this paper, we propose TAG, a Tree-Assisted Gossip protocol that addresses the above issues. TAG adopts a tree structure with time indexing to accommodate asynchronous requests, and an efficient pull-based gossip algorithm to mitigate the impact of network dynamicity. It seamlessly integrates these two approaches and realizes their best features, namely, low delay with a regular tree topology, and robust delivery with smart switching among multiple paths, thus making effective use of the available bandwidth in the network. We evaluate the performance of TAG under various settings, and the results demonstrate that it is quite robust in the presence of local and global bandwidth fluctuations. As compared to pure tree-based overlay VOD system, it achieves much lower and stable segment missing rates, even under highly dynamic network conditions.
18277516
Mesh Optimisation Using Edge Information in Feature-Based Surface Reconstruction
One of the most challenging and fundamental problems in computer vision is to reconstruct a surface model given a set of uncalibrated 2D images. Well-established Structure from Motion (SfM) algorithms often result in a sparse set of 3D surface points, but surface modelling based on sparse 3D points is not easy. In this paper, we present a new method to refine and optimise surface meshes using edge information in the 2D images. We design a meshing – edge point detection – re-meshing scheme that can gradually refine the surface mesh until it best fits the true physical surface of the object being modelled. Our method is tested on real images and satisfactory results are obtained.
5434773
Simulation validation using direct execution of wireless ad-hoc routing protocols
Computer simulation is the most common approach to studying wireless ad-hoc routing algorithms. The results, however, are only as good as the models the simulation uses. One should not underestimate the importance of validation, as inaccurate models can lead to wrong conclusions. In this paper, we use direct-execution simulation to validate radio models used by ad-hoc routing protocols, against real-world experiments. This paper documents a common testbed that supports direct execution of a set of ad-hoc routing protocol implementations in a wireless network simulator. The testbed reads traces generated from real experiments, and uses them to drive direct-execution implementations of the routing protocols. Doing so we reproduce the same network conditions as in real experiments. By comparing routing behavior measured in real experiments with behavior computed by the simulation, we are able to validate the models of radio behavior upon which protocol behavior depends. We conclude that it is possible to have fairly accurate results using a simple radio model, but the routing behavior is quite sensitive to one of this model's parameters. The implication is that one should: i) use a more complex radio model that explicitly models point-to-point path loss; or ii) use measurements from an environment typical of the one of interest; or iii) study behavior over a range of environments to identify sensitivities.
4908568
Insignificant shadow detection for video segmentation
To prevent moving cast shadows from being misunderstood as part of moving objects in change detection based video segmentation, this paper proposes a novel approach to the cast shadow detection based on the edge and region information in multiple frames. First, an initial change detection mask containing moving objects and cast shadows is obtained. Then a Canny edge map is generated. After that, the shadow region is detected and removed through multiframe integration, edge matching, and region growing. Finally, a post processing procedure is used to eliminate noise and tune the boundaries of the objects. Our approach can be used for video segmentation in indoor environment. The experimental results demonstrate its good performance.