Geodesic
(k − 2)-linear connected components in hypergraphs of rank k
Discrete mathematics & theoretical computer science, special issue ICGT'22, Tome 25 (2023-2024) no. 3.

Voir la notice de l'article provenant de la source Episciences

We define a q-linear path in a hypergraph H as a sequence (e_1,...,e_L) of edges of H such that |e_i ∩ e_i+1 | ∈ [[1, q]] and e_i ∩ e_j = ∅ if |i − j| > 1. In this paper, we study the connected components associated to these paths when q = k − 2 where k is the rank of H. If k = 3 then q = 1 which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph.
DOI : 10.46298/dmtcs.10202
Classification : 05C38, 05C65, 05C85 
@article{DMTCS_2024_25_3_a2,
     author = {Galliot, Florian and Gravier, Sylvain and Sivignon, Isabelle},
     title = {(k \ensuremath{-} 2)-linear connected components in hypergraphs of rank k},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2023-2024},
     doi = {10.46298/dmtcs.10202},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10202/}
}
TY  - JOUR
AU  - Galliot, Florian
AU  - Gravier, Sylvain
AU  - Sivignon, Isabelle
TI  - (k − 2)-linear connected components in hypergraphs of rank k
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10202/
DO  - 10.46298/dmtcs.10202
LA  - en
ID  - DMTCS_2024_25_3_a2
ER  - 
%0 Journal Article
%A Galliot, Florian
%A Gravier, Sylvain
%A Sivignon, Isabelle
%T (k − 2)-linear connected components in hypergraphs of rank k
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10202/
%R 10.46298/dmtcs.10202
%G en
%F DMTCS_2024_25_3_a2
Galliot, Florian; Gravier, Sylvain; Sivignon, Isabelle. (k − 2)-linear connected components in hypergraphs of rank k. Discrete mathematics & theoretical computer science, special issue ICGT'22, Tome 25 (2023-2024) no. 3. doi : 10.46298/dmtcs.10202. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10202/

Cité par Sources :