Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

D 2022

Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

BALABÁN, Jakub, Petr HLINĚNÝ a Jan JEDELSKÝ

Základní údaje

Originální název

Twin-Width and Transductions of Proper k-Mixed-Thin Graphs

Autoři

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

Vydání

LNCS 13453. Cham, WG 2022: Graph-Theoretic Concepts in Computer Science, od s. 43-55, 13 s. 2022

Nakladatel

Springer Nature

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Švýcarsko

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/22:00127036

Organizační jednotka

Fakulta informatiky

ISBN

978-3-031-15913-8

ISSN

DOI

http://dx.doi.org/10.1007/978-3-031-15914-5_4

UT WoS

000866013700004

Klíčová slova anglicky

twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 3. 2023 12:02, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

The new graph parameter twin-width, recently introduced by Bonnet et al., allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, such classes (of small twin-width) include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a certain subclass of k-mixed-thin graphs is transduction-equivalent to posets of width 𝑘′ such that there is a quadratic relation between k and 𝑘′.

Návaznosti

GA20-04567S, projekt VaV

Název: Struktura efektivně řešitelných případů těžkých algoritmických problémů na grafech

Investor: Grantová agentura ČR, Structure of tractable instances of hard algorithmic problems on graphs

MUNI/A/1145/2021, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Akronym: SV-FI MAV XI.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.

MUNI/A/1230/2021, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 22 (Akronym: SKOMU)

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

Citovat

BALABÁN, Jakub, Petr HLINĚNÝ a Jan JEDELSKÝ. Twin-Width and Transductions of Proper k-Mixed-Thin Graphs. In Michael A. Bekos and Michael Kaufmann. WG 2022: Graph-Theoretic Concepts in Computer Science. LNCS 13453. Cham: Springer Nature, 2022, s. 43-55. ISBN 978-3-031-15913-8. Dostupné z: https://dx.doi.org/10.1007/978-3-031-15914-5_4.

@inproceedings{2227560,
   author = {Balabán, Jakub and Hliněný, Petr and Jedelský, Jan},
   address = {Cham},
   booktitle = {WG 2022: Graph-Theoretic Concepts in Computer Science},
   doi = {http://dx.doi.org/10.1007/978-3-031-15914-5_4},
   edition = {LNCS 13453},
   editor = {Michael A. Bekos and Michael Kaufmann},
   keywords = {twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-031-15913-8},
   pages = {43-55},
   publisher = {Springer Nature},
   title = {Twin-Width and Transductions of Proper k-Mixed-Thin Graphs},
   url = {https://link.springer.com/chapter/10.1007/978-3-031-15914-5_4},
   year = {2022}
}

TY  - JOUR
ID  - 2227560
AU  - Balabán, Jakub - Hliněný, Petr - Jedelský, Jan
PY  - 2022
TI  - Twin-Width and Transductions of Proper k-Mixed-Thin Graphs
PB  - Springer Nature
CY  - Cham
SN  - 9783031159138
KW  - twin-width;proper interval graph;proper mixed-thin graph;transduction equivalence
UR  - https://link.springer.com/chapter/10.1007/978-3-031-15914-5_4
N2  - The new graph parameter twin-width, recently introduced by Bonnet et al., allows for an FPT algorithm for testing all FO properties of graphs. This makes classes of efficiently bounded twin-width attractive from the algorithmic point of view. In particular, such classes (of small twin-width) include proper interval graphs, and (as digraphs) posets of width k. Inspired by an existing generalization of interval graphs into so-called k-thin graphs, we define a new class of proper k-mixed-thin graphs which largely generalizes proper interval graphs. We prove that proper k-mixed-thin graphs have twin-width linear in k, and that a certain subclass of k-mixed-thin graphs is transduction-equivalent to posets of width 𝑘′ such that there is a quadratic relation between k and 𝑘′.
ER  -

BALABÁN, Jakub, Petr HLINĚNÝ a Jan JEDELSKÝ. Twin-Width and Transductions of Proper k-Mixed-Thin Graphs. In Michael A. Bekos and Michael Kaufmann. \textit{WG 2022: Graph-Theoretic Concepts in Computer Science}. LNCS 13453. Cham: Springer Nature, 2022, s.~43-55. ISBN~978-3-031-15913-8. Dostupné z: https://dx.doi.org/10.1007/978-3-031-15914-5\_{}4.

Podrobný výpis o publikaci