Planar Graphs Have Bounded Queue-Number Dujmović, Vida; Joret, Gwenaël; Micek, Piotr ...
Journal of the ACM,
08/2020, Letnik:
67, Številka:
4
Journal Article
Recenzirano
Odprti dostop
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al. 66 from 1992. The key to the proof is a new structural tool called
layered partitions
, and the result ...that every planar graph has a vertex-partition and a layering, such that each part has a bounded number of vertices in each layer, and the quotient graph has bounded treewidth. This result generalises for graphs of bounded Euler genus. Moreover, we prove that every graph in a minor-closed class has such a layered partition if and only if the class excludes some apex graph. Building on this work and using the graph minor structure theorem, we prove that every proper minor-closed class of graphs has bounded queue-number.
Layered partitions have strong connections to other topics, including the following two examples. First, they can be interpreted in terms of strong products. We show that every planar graph is a subgraph of the strong product of a path with some graph of bounded treewidth. Similar statements hold for all proper minor-closed classes. Second, we give a simple proof of the result by DeVos et al. 31 that graphs in a proper minor-closed class have low treewidth colourings.
•We derive point queue models as limits of link-based queueing models.•We provide two definitions of demand and supply of a point queue.•We present four point queue models, four approximate models, ...and discrete versions.•We analytically solve Vickrey’s point queue model and stationary states in all models.•All existing point queue models are shown to be special cases of proposed models.
In transportation and other types of facilities, various queues arise when the demands of service are higher than the supplies, and many point and fluid queue models have been proposed to study such queueing systems. However, there has been no unified approach to deriving such models, analyzing their relationships and properties, and extending them for networks. In this paper, we derive point queue models as limits of two link-based queueing model: the link transmission model and a link queue model. With two definitions for demand and supply of a point queue, we present four point queue models, four approximate models, and their discrete versions. We discuss the properties of these models, including equivalence, well-definedness, smoothness, and queue spillback, both analytically and with numerical examples. We then analytically solve Vickrey’s point queue model and stationary states in various models. We demonstrate that all existing point and fluid queue models in the literature are special cases of those derived from the link-based queueing models. Such a unified approach leads to systematic methods for studying the queueing process at a point facility and will also be helpful for studies on stochastic queues as well as networks of queues.
Edge computing applications typically require generated data to be preprocessed at the source and then transmitted to an edge server. In such cases, transmission time and preprocessing time are ...coupled, yielding a tradeoff between them to achieve the targeted objective. This paper presents analysis of such a system with the objective of optimizing freshness of received data at the edge server. We model this system as two queues in tandem whose service times are independent but the transmission service time is monotonically dependent on the computation service time in mean value. This dependence captures the natural decrease in transmission time due to lower offloaded computation. We analyze various queue management schemes in this tandem queue where the compute queue has a single server, Poisson packet arrivals, general independent service and no extra buffer to save incoming packets. The transmit queue has a single server receiving packets from the compute queue with memoryless service time. We consider the transmit queue in two forms: (i) No data buffer and (ii) One unit data buffer and last come first serve with discarding. We analyze various non-preemptive as well as preemptive cases. We perform stationary distribution analysis and obtain closed form expressions for average age of information (AoI) and average peak AoI. Our numerical results illustrate analytical findings on how computation and transmission times could be traded off to optimize AoI and reveal a consequent tradeoff between average AoI and average peak AoI.
We study three non-equivalent queueing models in continuous time that each generalise the classical M/M/1 queue in a different way. Inter-event times in all models are Mittag-Leffler distributed, ...which is a heavy tail distribution with no moments. For each of the models we answer the question of the queue being at zero infinitely often (the ‘recurrence’ regime) or not (the transient regime). Aside from this question, the different analytical properties of each models allow us to answer a number of questions such as existence and description of equilibrium distributions, mixing times, asymptotic behaviour of return probabilities and moments and functional limit theorems.
•Short vehicle trajectories are collected and used from mobile sensors.•Missing acceleration/deceleration process is estimated from short vehicle trajectories.•Models are trained using sample short ...vehicle trajectories from multiple cycles.•The queue profile and maximum queue length of a cycle can be estimated.
Queue length is one of the key measures in assessing arterial performances. Under heavy congestion, queues are difficult to estimate from either fixed-location sensors (such as loop detectors) or mobile sensors since they may exceed the region of detection, which is defined as long queue in the literature. While the long queue problem has been successfully addressed in the past using fixed-location sensors, whether this can be done using mobile traffic sensors remains unclear. In this paper, a queue length estimation method is proposed to solve this long queue problem using short vehicle trajectories obtained from mobile sensors. The method contains vehicle trajectory reconstruction models to estimate the missing deceleration or acceleration process of a vehicle. Long queue estimation models are then developed using the reconstructed vehicle trajectories. The proposed method can provide estimates of the queue profile and the maximum queue length of a cycle. The method is tested in a field experiment with reasonable results.
Dynamic resource control and routing are important for realising the intelligent control of data transmission in wireless multi-hop networks. It is well known that back-pressure routing based on a ...max-weight policy maximises network throughput and optimises resource allocation in multi-hop wireless networks with time-varying channels. Due to the slow routing convergence and complex control of data queues, however, back-pressure routing also results in large end-to-end delays and a waste of network resources, particularly when the network loads are light or moderate. In this study, a differential back-pressure routing scheme with single-queue management is proposed to improve the packet delay performance and simplify the management of data queues. Unlike in traditional back-pressure routing, the authors use the differences in the rates of change in data queue length to calculate data pressure. Compared with the method of data backlog calculation based on queue length differences, this method achieves faster routing convergence. They also consider the ceiling problem for a single queue and enhance the effect of the queue cap on the routing metric by means of dynamic weighting. Simulation results show that the proposed routing algorithm achieves a 20% decrease in end-to-end delay in grid and random networks.
•Discriminant models and Kalman filters are used to estimate lane-based queue lengths.•Once calibrated, commonly available detector data are used to estimate queue lengths.•Simulations and case ...studies demonstrate the effectiveness of the proposed method.
In this study, we develop a real-time estimation approach for lane-based queue lengths. Our aim is to determine the numbers of queued vehicles in each lane, based on detector information at isolated signalized junctions. The challenges involved in this task are to identify whether there is a residual queue at the start time of each cycle and to determine the proportions of lane-to-lane traffic volumes in each lane. Discriminant models are developed based on time occupancy rates and impulse memories, as calculated by the detector and signal information from a set of upstream and downstream detectors. To determine the proportions of total traffic volume in each lane, the downstream arrivals for each cycle are estimated by using the Kalman filter, which is based on upstream arrivals and downstream discharges collected during the previous cycle. Both the computer simulations and the case study of real-world traffic show that the proposed method is robust and accurate for the estimation of lane-based queue lengths in real time under a wide range of traffic conditions. Calibrated discriminant models play a significant role in determining whether there are residual queued vehicles in each lane at the start time of each cycle. In addition, downstream arrivals estimated by the Kalman filter enhance the accuracy of the estimates by minimizing any error terms caused by lane-changing behavior.
•First passage densities for time-inhomogeneous birth-death (BD) chains and restricted BD processes.•Volterra integral equations.•Computational algorithms.•Extinction density and busy period ...density.•Polya BD process.•Gompertz BD process.•Linear BD processes with immigration.•M(t)/M(t)/∞ queueing system.•M(t)/M(t)/1 queueing system.
New integral equations are proposed to determine first-passage-time densities for time-inhomogeneous birth-death processes. Such equations, particularly suitable for computational purposes, are also used to obtain closed-form expressions for the first-passage-time densities of special birth-death processes of interest in various application fields.
Mobile cloud computing (MCC) broadens the mobile devices capability by offloading tasks to the ‘cloud’. Hence, offloading numerous tasks simultaneously increases the ‘cloudlets’ load and augments the ...average completion duration of the offloaded tasks. To withstand this issue, we propose a hybrid Queue Ant Colony-Artificial Bee Colony Optimization (Ant-Bee) algorithm for optimal assignment of tasks in MCC environment. The proposed algorithm works on a two-way MCC model with offloading technique, that considers of both the ‘cloudlets’ and the public ‘cloud’. The ‘cloud’ and the ‘cloudlets’ are designed on the basis of queue model for the estimation of clients waiting time in the limitation of resources. The major concern of the proposed algorithm is to offload the tasks by identifying the accurate place preferably in a ‘cloud/cloudlet’. The ‘cloud/cloudlet’ is encompassed by a queue model with the end goal to minimize the drop rate by permitting the tasks to wait in the queue. It also aims for the optimal assignment of tasks to manage the ‘cloudlets’ load and to minimize the entire tasks average completion time. The performance of the proposed algorithm is analyzed with few Queue based conventional algorithms such as, “Round Robin”, “Weighted Round Robin” and “Random”. From the simulation result, it is analyzed that our proposed algorithm outperforms in the power consumption of the mobile devices, the average completion time of tasks, and drop rate. Also, to ensure the efficiency of our proposed hybrid
QAnt
-
Bee
algorithm, it is contrasted with the “HACAS” application scheduling algorithm, which fails to consider queue in the ‘cloudlets’.
Development of highly stabilized and reversible cathode materials has become a great challenge for sodium‐ion batteries. O′3‐type layered Mn‐based oxides have deserved much attention as one of ...largely reversible‐capacity cathodes featured by the resource‐rich and low‐toxic elements. However, the fragile slabs structure of typical layered oxides, low Mn‐ion migration barriers, and Jahn–Teller distortion of Mn3+ have easily resulted in the severe degradation of cyclability and rate performances. Herein, a new queue‐ordered superstructure is built up in the O′3‐NaMn0.6Al0.4O2 cathode material. Through the light‐metal Al substitution in O′3‐NaMnO2, the MnO6 and AlO6 octahedrons display the queue‐ordered arrangements in the transition metal (TM) slabs. Interestingly, the presence of this superstructure can strengthen the layered structure, reduce the influence from Jahn–Teller effect, and suppress the TM‐ions migrations during long‐terms cycles. These characteristics results in O′3‐NaMn0.6Al0.4O2 cathode deliver a high capacity of 160 mAh g−1, an enhanced rate capability and the excellent cycling performance. This research strategy can provide the broaden insight for future electrode materials with high‐performance sodium‐ions storage.
A novel queue‐order NaMn0.6Al0.4O2 (NMA) is first prepared as high‐performance cathode material for sodium‐ion battery. The NMA exhibits a firmed layered structure based on queue‐ordered Mn0.6Al0.4O2 slabs, which result in NMA cathode delivers a high practical capacity of 160 mAh g−1, a remarkable rate performance and an excellent cycling life of 81% retention after 100 cycles.
PDF
