D 2023

Stack and Queue Numbers of Graphs Revisited

HLINĚNÝ, Petr a Adam STRAKA

Základní údaje

Originální název

Stack and Queue Numbers of Graphs Revisited

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Adam STRAKA (703 Slovensko, domácí)

Vydání

Brno, Czech Republic, European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23, od s. 601-606, 6 s. 2023

Nakladatel

MUNI Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/23:00131121

Organizační jednotka

Fakulta informatiky

ISSN

DOI

Klíčová slova anglicky

linear layout; stack number; queue number

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 22. 3. 2024 07:59, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmović and Wood in 2005, was ``half-answered‘‘ by Dujmović, 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. We give an alternative very short, and still elementary, proof of the same fact.

Návaznosti

MUNI/A/1081/2022, interní kód MU
Název: Modelování, analýza a verifikace (2023)
Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)