Search

Full-duplex (FD) transmission in a point-to-point (P2P) link, wherein bidirectional traffic flows simultaneously share the same spectrum, has the capability of doubling the link rate by completely removing self-interferences. However, the rate performance of an FD heterogeneous network (HetNet) is not as clear as that of an FD P2P link due to the co-channel interferences induced by the complex FD and half-duplex (HD) transmission behaviors in the HetNet. To thoroughly investigate the achievable link rate performances of users and base stations (BSs) in a HetNet with decoupled user association, a hybrid-duplex approach is proposed to model a HetNet in which all BSs and users can perform HD or FD transmission depending on their traffic patterns. We first characterize the decoupled rate-optimal user association scheme and use it to define and evaluate the downlink and uplink rates in the HetNet. The tight lower bounds on the link rates of the FD users and BSs are found in a neat form that characterizes general channel fading, imperfect self-interference cancellation, and the intensities of users and BSs. These bounds outline the rate regions of the FD users that inspire us to propose the opportunistic FD scheduling algorithms that maximize the sum rate of each bidirectional traffic and stabilize each of the queues in the HetNet. [ABSTRACT FROM AUTHOR]

For nonnegative integers k, d1, . . ., dk, a graph is (d1, . . ., dk)-colorable if its vertex set can be partitioned into k parts so that the ith part induces a graph with maximum degree at most di for all i ∊ {1, . . ., k}. A class C of graphs is balanced k-partitionable and unbalanced k-partitionable if there exists a nonnegative integer D such that all graphs in C are (D, . . .,D)- colorable and (0, . . ., 0,D)-colorable, respectively, where the tuple has length k. A set X of cycles is a cycle obstruction set of a class C of planar graphs if every planar graph containing none of the cycles in X as a subgraph belongs to C. This paper characterizes all cycle obstruction sets of planar graphs to be balanced k-partitionable and unbalanced k-partitionable for all k, namely, we identify all inclusionwise minimal cycle obstruction sets for all k. [ABSTRACT FROM AUTHOR]

An (a : b)-coloring of a graph G is a function f which maps the vertices of G into b-element subsets of some set of size a in such a way that f(u) is disjoint from f(v) for every two adjacent vertices u and v in G. The fractional chromatic number χf(G) is the infimum of a/b over all pairs of positive integers a, b such that G has an (a : b)-coloring. Heckman and Thomas conjectured that the fractional chromatic number of every triangle-free graph G of maximum degree at most three is at most 2.8. Hatami and Zhu proved that χf/(G) ≤ 3 - 3/64 ≤ 2.953. Lu and Peng improved the bound to χf(G) ≤ 3 - 3/64≈ 2.930. Recently, Ferguson, Kaiser, and Krai' proved that Xf(G) ≤ 32/11 ≈ 2.909. In this paper, we prove that χf(G) ≤ 43/15 ≈ 2.867. [ABSTRACT FROM AUTHOR]

A Roman dominating function of a graph G is a function f: V (G) → {0, 1, 2} such that whenever f(v) = 0, there exists a vertex u adjacent to v such that f(u)=2 . T h e weight of f is w(f)= f(v). Σ∈V(G) f(v). The Roman domination number γR (G) of G is the minimum weight of a Roman dominating function of G. Chambers, Kinnersley, Prince, and West [ SIAM J. Discrete Math., 23 (2009), pp. 1575-1586] conjectured that γR(G) ≤ [2n/3] for any 2-connected graph G of n vertices. This paper gives counterexamples to the conjecture and proves that γR(G) ≤ max{[2n/3], 23n/34} for any 2-connected graph G of n vertices. We also characterize 2-connected graphs G for which γR(G)=23n/34 when 23n/34 > 2n/3. [ABSTRACT FROM AUTHOR]

Electron-beam-direct-write lithography has been considered a candidate next-generation technique for achieving high resolution. An accurate point spread function (PSF) is essential for reliable patterning prediction and proximity-effects correction. It can be derived via an effective parametric PSF calibration methodology, typically involving the fitting of the absorbed energy distribution (AED) from an electron-scattering simulation. However, the existing parametric PSF calibration methodology does not employ a systematic approach to obtain a new PSF form that is both compact and accurate when conventional PSF forms are not satisfactory. Only the AED fitting quality (rather than its patteming-prediction quality) is considered during the conventional calibration methodology. It also lacks a process to consider whether the predicted deviation (as simulated using the chosen PSF form) is satisfactory. This paper proposes a new parametric PSF calibration methodology to systematically obtain a PSF form consisting of the smallest number of terms, with a better combination of basis functions and that optimizes pattern accuracy. The effectiveness of using the new methodology is demonstrated in terms of fitting accuracy, patterning-prediction accuracy, and patterning sensitivity. [ABSTRACT FROM AUTHOR]

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minor-closed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad-Nagata dimension at most 2. Furthermore, our techniques allow us to determine the asymptotic dimension of graphs of bounded layered treewidth and graphs with any fixed growth rate, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours. [ABSTRACT FROM AUTHOR]

The asymptotic dimension is an invariant of metric spaces introduced by Gromov in the context of geometric group theory. In this paper, we study the asymptotic dimension of metric spaces generated by graphs and their shortest path metric and show their applications to some continuous spaces. The asymptotic dimension of such graph metrics can be seen as a large scale generalisation of weak diameter network decomposition which has been extensively studied in computer science. We prove that every proper minor-closed family of graphs has asymptotic dimension at most 2, which gives optimal answers to a question of Fujiwara and Papasoglu and (in a strong form) to a problem raised by Ostrovskii and Rosenthal on minor excluded groups. For some special minorclosed families, such as the class of graphs embeddable in a surface of bounded Euler genus, we prove a stronger result and apply this to show that complete Riemannian surfaces have Assouad--Nagata dimension at most 2. Furthermore, our techniques allow us to determine the asymptotic dimension of graphs of bounded layered treewidth and graphs with any fixed growth rate, which are graph classes that are defined by purely combinatorial notions and properly contain graph classes with some natural topological and geometric flavours. [ABSTRACT FROM AUTHOR]

Low-energy electron beam lithography is one of the promising next-generation lithography technology solutions for the 21-nm half-pitch node and beyond because of fewer proximity effects, higher resist sensitivity, and less substrate damage compared with high-energy electron beam lithography. To achieve high-throughput manufacturing, low-energy electron beam lithography systems with writing parameters of larger beam size, larger grid size, and lower dosage are preferred. However, electron shot noise can significantly increase critical dimension deviation and line edge roughness. Its influence on patteming prediction accuracy becomes nonnegligible. To effectively maximize throughput while meeting patterning fidelity requirements according to the International Technology Roadmap for Semiconductors, a new method is proposed in this work that utilizes a new patterning prediction algorithm to rigorously characterize the patterning variability caused by the shot noise and a mathematical optimization algorithm to determine optimal writing parameters. The new patteming prediction algorithm can achieve a proper trade-off between computational effort and patterning prediction accuracy. Effectiveness of the new method is demonstrated on a static random-access memory circuit. The corresponding electrical performance is analyzed by using a gate-slicing technique and publicly available transistor models. Numerical results show that a significant improvement in the static noise margin can be achieved. [ABSTRACT FROM AUTHOR]

Rate-distortion (RD)-based mode selections are important techniques in video coding. In these methods, an encoder may compute the RD costs for all the possible coding modes, and select the one which achieves the best trade-off between encoding rate and compression distortion. Previous papers have demonstrated that RD-based mode selections can lead to significant improvements in coding efficiency. RD-based mode selections, however, would incur considerable increases in encoding complexity, since these methods require computing the RD costs for numerous candidate coding modes. In this paper, we consider the scenario where software-based video encoding is performed on personal computers or game consoles, and investigate how multicore graphics processing units (GPUs) may be efficiently utilized to undertake the task of RD optimized intra-prediction mode selections in audio and video coding standards and H.264 video encoding. Achieving efficient GPU-based intra-mode decisions, however, could be nontrivial for two reasons. First, intra-mode decision tends to be sequential. Specifically, the mode decision of the current block would depend on the reconstructed data of the neighboring blocks. Therefore, the coding modes of neighboring blocks would need to be computed first before that of the current block can be determined. This dependency poses challenges to GPU-based computation, which relies heavily on parallel data processing to achieve superior speedups. Second, RD-based intra- mode decision may require conditional branchings to determine the encoding bit-rate, and these branching operations may incur substantial performance penalties when being executed on GPUs due to pipeline architectural designs. To address these issues, we analyze the data dependency in intra-mode decision, and propose novel greedy-based encoding orders to achieve highly parallel processing of data blocks. We also prove that the proposed greedy-based orders are optimal in our problem, i.e., they require the minimum number of iterations to process a video frame given the dependency constraints. In addition, we propose a method to estimate the coding rate suitable for GPU implementation. Experimental results suggest our proposed solution can be more than 50 times faster than the previously proposed parallel intra- prediction, since our work can efficiently exploit the massive parallel opportunity in GPUs. [ABSTRACT FROM AUTHOR]