73 research outputs found
Recommended from our members
Investigation of 4-cutwidth critical graphs
No full textA 2004 article written by Yixun Lin and Aifeng Yang published in the journal Discrete Math characterized the set of a 3-cutwidth critical graphs by five specified elements. This project extends the idea to 4-cutwidth critical graphs
New bounds on the edge-bandwidth of triangular grids
No full textThe edge-bandwidth of a graph G is the bandwidth of the line graph of G. Determining the edge-bandwidth B′(Tn) of triangular grids Tn is an open problem posed in 2006. Previously, an upper bound and an asymptotic lower bound were found to be 3n − 1 and 3n − o(n) respectively. In this paper we provide a lower bound 3n − ⌈ n/ 2 ⌉ and show that it gives the exact values of B′(Tn) for 1 ≤ n ≤ 8 and n = 10. Also, we show the upper bound 3n − 5 for n ≥ 10
Cutwidth of iterated caterpillars
No full textThe cutwidth is an important graph-invariant in circuit layout designs. The cutwidth of a
graph G is the minimum value of the maximum number of overlap edges when
G is embedded into a line. A caterpillar is a tree which yields a path
when all its leaves are removed. An iterated caterpillar is a tree which yields a
caterpillar when all its leaves are removed. In this paper we present an exact formula for
the cutwidth of the iterated caterpillars
Square-root rule of two-dimensional bandwidth problem
No full textThe bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root rule” of the two-dimensional bandwidth, which is useful in evaluating B2(G) for some typical graphs
Integrated Communication and Sensing with RGB LEDs
No full textVisible Light Communication (VLC) has gained popularity due to its inherent security as a complementary technology to Radio Frequency (RF) in the last decades to solve the "spectrum crunch'' problem. Meanwhile, The latest IEEE 802.11ah standard, also called WiFi HaLow, offers the range, throughput, and low power consumption that is extremely suitable for most simple IoT appliances for industrial, agricultural, and smart city environments. In general, these IoT products are connected in huge numbers. Hence, provisioning these simple IoT products that usually do not have any user interface like a keyboard or a display in a simple, robust, secure, and scalable method is a significant challenge.VLC technology has been intriguing both industry and academia for connecting IoT products over the last few years. The signals used in VLC, the visible light, can be captured by eyes and be confined by walls and other blockages which introduce the security against eavesdropping. Besides, the features of low deployment cost, high throughput and high security make VLC a solution to provision IoT products securely. This project exploits on-device existing RGB LEDs to achieve a low-cost and secure device provision system called Integrated Visible Light Communication and Sensing (I-VLCS) System with the functionality of the integrated communication and sensing with RGB LEDs. Visible Light Positioning (VLP), a subset of Visible Light Sensing, is also used in the I-VLCS system to further improve the system security. The performance of the proposed I-VLCS system is evaluated through experiments, demonstrating that that the system can support a maximum 50 cm of communication range with a high communication and positioning accuracy.Electrical Engineering | Embedded System
On 3-cutwidth critical graphs
No full textAbstractThe cutwidth of a graph G is the minimum congestion (the number of overlap edges) when G is embedded into a path. The cutwidth problem has been motivated from both applied and theoretical points of view. The characterization of forbidden subgraphs or critical graphs is always interesting in the study of a graph-theoretic parameter. In this paper we characterize the set of 3-cutwidth critical graphs by five specified elements
Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria
No full text
- …
