ℋ-Clique-Width and a Hereditary Analogue of Product Structure

D 2024

ℋ-Clique-Width and a Hereditary Analogue of Product Structure

HLINĚNÝ, Petr a Jan JEDELSKÝ

Základní údaje

Originální název

ℋ-Clique-Width and a Hereditary Analogue of Product Structure

Autoři

HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Jan JEDELSKÝ (203 Česká republika, domácí)

Vydání

Dagstuhl, Germany, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), od s. "61:1"-"61:16", 16 s. 2024

Nakladatel

Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-335-5

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.MFCS.2024.61

Klíčová slova anglicky

product structure; hereditary class; clique-width; twin-width

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 1. 9. 2024 12:03, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-width. Furthermore, every graph admitting the usual (non-induced) product structure of a path times a graph of bounded tree-width, has bounded H-clique-width and, as a consequence, it admits the usual product structure in an induced way. We prove further basic properties of H-clique-width in general.

Návaznosti

MUNI/A/1592/2023, interní kód MU

Název: Modelování, analýza a verifikace (2024)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2024)

MUNI/A/1608/2023, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Citovat

HLINĚNÝ, Petr a Jan JEDELSKÝ. ℋ-Clique-Width and a Hereditary Analogue of Product Structure. Online. In Královič, Rastislav and Kučera, Antonín. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2024, s. "61:1"-"61:16", 16 s. ISBN 978-3-95977-335-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2024.61.

@inproceedings{2427157,
   author = {Hliněný, Petr and Jedelský, Jan},
   address = {Dagstuhl, Germany},
   booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
   doi = {http://dx.doi.org/10.4230/LIPIcs.MFCS.2024.61},
   editor = {Královič, Rastislav and Kučera, Antonín},
   keywords = {product structure; hereditary class; clique-width; twin-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-335-5},
   pages = {"61:1"-"61:16"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {ℋ-Clique-Width and a Hereditary Analogue of Product Structure},
   year = {2024}
}

TY  - JOUR
ID  - 2427157
AU  - Hliněný, Petr - Jedelský, Jan
PY  - 2024
TI  - ℋ-Clique-Width and a Hereditary Analogue of Product Structure
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl, Germany
SN  - 9783959773355
KW  - product structure
KW  - hereditary class
KW  - clique-width
KW  - twin-width
N2  - We introduce a novel generalization of the notion of clique-width which aims to bridge the gap between classical hereditary width measures and the recently introduced graph product structure theory. Bounding the new H-clique-width, in the special case of H being the class of paths, is equivalent to admitting a hereditary (i.e., induced) product structure of a path times a graph of bounded clique-width. Furthermore, every graph admitting the usual (non-induced) product structure of a path times a graph of bounded tree-width, has bounded H-clique-width and, as a consequence, it admits the usual product structure in an induced way. We prove further basic properties of H-clique-width in general.
ER  -

HLINĚNÝ, Petr a Jan JEDELSKÝ. ℋ-Clique-Width and a Hereditary Analogue of Product Structure. Online. In Královič, Rastislav and Kučera, Antonín. \textit{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2024, s.~''61:1''-''61:16'', 16 s. ISBN~978-3-95977-335-5. Dostupné z: https://dx.doi.org/10.4230/LIPIcs.MFCS.2024.61.

Podrobný výpis o publikaci