Results 1 to 10 of about 20,892 (173)
Bounded-Degree Graphs have Arbitrarily Large Queue-Number [PDF]
Discrete Mathematics & Theoretical Computer Science, 2008 It is proved that there exist graphs of bounded degree with arbitrarily large queue-number. In particular, for all Δ ≥ 3 and for all sufficiently large n, there is a simple Δ-regular n-vertex graph with queue-number at least c √ Δ n 1/2-1/Δ for ...
David R. Wood
doaj +6 more sources
Discrete Mathematics & Theoretical Computer Science, 2004 A \emph(k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross.
Vida Dujmović +2 more
doaj +7 more sources
Stack-Number is Not Bounded by Queue-Number [PDF]
Combinatorica, 2021 We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999).
Dujmović, Vida +4 more
openaire +2 more sources
On the Queue Number of Planar Graphs [PDF]
, 2021 A k-queue layout is a special type of a linear layout, in which the linear order avoids (k+1)-rainbows, i.e., k+1 independent edges that pairwise form a nested pair. The optimization goal is to determine the queue number of a graph, i.e., the minimum value of k for which a k-queue layout is feasible. Recently, Dujmovi et al. [J.
Michael A. Bekos +2 more
openaire +3 more sources
Planar Graphs have Bounded Queue-Number [PDF]
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019 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 ...
Dujmović, Vida V. +5 more
openaire +10 more sources
Stacks, Queues and Tracks: Layouts of Graph Subdivisions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 A \emphk-stack layout (respectively, \emphk-queuelayout) of a graph consists of a total order of the vertices, and a partition of the edges into k sets of non-crossing (non-nested) edges with respect to the vertex ordering.
Vida Dujmović, David R. Wood
doaj +3 more sources
On the Queue-Number of Partial Orders [PDF]
, 2021 Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021)
Felsner, Stefan +2 more
openaire +3 more sources
RANCANG BANGUN SISTEM NOMER ANTRIAN BERBASIS INTERNET OF THINGS (IOT)
Jurnal Saintekom, 2022 Queuing is a phenomenon that we can encounter anywhere and anytime, such as queuing to get food orders, ticketing services, and so on. However, unfortunately not everyone likes to queue, especially queuing for public agency services.
I Made Agus Chandra Wijaya +1 more
doaj +1 more source
An Analysis of the “Horizontal Y” Shaped Queuing Model to Assist in Health Care Institution [PDF]
International Journal Bioautomation, 2023 The “Horizontal Y” shaped queuing model in which there is bulk infinite arrival of patients, but available M services are limited. The discrete flow of patients in the system is reduced in continuous flow and a diffusion equation is used.
Manish Kumar Pandey +1 more
doaj +1 more source
Stack and queue numbers of graphs revisited
European Journal of Combinatorics, 2023 A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmovi\'c and Wood in 2005, was ``half-answered'' by Dujmovi\'c, Eppstein, Hickingbotham, Morin and Wood in 2022; they proved the existence of a graph family with the queue number at most $4$ but unbounded stack number.
Petr Hliněný, Adam Straka
openaire +3 more sources