ℋ-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 a Jan JEDELSKÝ

Vydání

LIPIcs Vol. 306. 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"

Kód RIV

RIV/00216224:14330/24:00136980

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-335-5

ISSN

DOI

https://doi.org/10.4230/LIPIcs.MFCS.2024.61

EID Scopus

2-s2.0-85203360924

Klíčová slova anglicky

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

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 3. 2025 13:35, 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). LIPIcs Vol. 306. 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://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 = {https://doi.org/10.4230/LIPIcs.MFCS.2024.61},
   edition = {LIPIcs Vol. 306},
   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  - CONF
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)}. LIPIcs Vol. 306. 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://doi.org/10.4230/LIPIcs.MFCS.2024.61.

Přehled o publikaci