Geodesic
Certifying Induced Subgraphs in Large Graphs
Ulrich Meyer1 ; Hung Tran1 ; Konstantinos Tsakalidis2
1 Goethe University Frankfurt and Frankfurt Institute for Advanced Studies
2 University of Liverpool and Athena Research Center
Journal of Graph Algorithms and Applications, Special issue on Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 , Tome 28 (2024) no. 3, pp. 49-68.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We introduce I/O-efficient certifying algorithms for the recognition of bipartite, split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class.Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership.On a graph with $n$ vertices and $m$ edges, our algorithms take $\mathcal O(\text{sort}(n + m))$ I/Os in the worst case for split, threshold and trivially perfect graphs.In the same complexity bipartite and bipartite chain graphs can be certified with high probability.We provide implementations and an experimental evaluation for split and threshold graphs.
DOI : 10.7155/jgaa.v28i3.2971
Keywords: I/O-efficient certifying algorithms

Ulrich Meyer 1 ; Hung Tran 1 ; Konstantinos Tsakalidis 2

1 Goethe University Frankfurt and Frankfurt Institute for Advanced Studies
2 University of Liverpool and Athena Research Center 
@article{JGAA_2024_28_3_a4,
     author = {Ulrich Meyer and Hung Tran and Konstantinos Tsakalidis},
     title = {Certifying {Induced} {Subgraphs} in {Large} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {49--68},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2024},
     doi = {10.7155/jgaa.v28i3.2971},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2971/}
}
TY  - JOUR
AU  - Ulrich Meyer
AU  - Hung Tran
AU  - Konstantinos Tsakalidis
TI  - Certifying Induced Subgraphs in Large Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2024
SP  - 49
EP  - 68
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2971/
DO  - 10.7155/jgaa.v28i3.2971
LA  - en
ID  - JGAA_2024_28_3_a4
ER  - 
%0 Journal Article
%A Ulrich Meyer
%A Hung Tran
%A Konstantinos Tsakalidis
%T Certifying Induced Subgraphs in Large Graphs
%J Journal of Graph Algorithms and Applications
%D 2024
%P 49-68
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2971/
%R 10.7155/jgaa.v28i3.2971
%G en
%F JGAA_2024_28_3_a4
Ulrich Meyer; Hung Tran; Konstantinos Tsakalidis. Certifying Induced Subgraphs in Large Graphs. Journal of Graph Algorithms and Applications, 
							Special issue on  Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023
					, Tome 28 (2024) no. 3, pp. 49-68. doi : 10.7155/jgaa.v28i3.2971. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.v28i3.2971/

Cité par Sources :