HLINĚNÝ, Petr a Adam STRAKA. Stack and Queue Numbers of Graphs Revisited. Online. In European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23. Brno, Czech Republic: MUNI Press, 2023, s. 601-606. ISSN 2788-3116. Dostupné z: https://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-083.
Další formáty:   BibTeX LaTeX RIS
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
Originální 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 2788-3116
Doi http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-083
Klíčová slova anglicky linear layout; stack number; queue number
Štítky formela-conference
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Petr Hliněný, Ph.D., učo 168881. Změněno: 22. 3. 2024 07:59.
Anotace
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 MUNázev: Modelování, analýza a verifikace (2023)
Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)
VytisknoutZobrazeno: 27. 4. 2024 16:23