Geodesic
Decycling bipartite graphs
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 461-480.

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

Let $G=(V,E)$ be a graph and let $S\subseteq V$ be a subset of its vertices. If the subgraph of $G$ induced by $V\setminus S$ is acyclic, then $S$ is said to be a decycling set of $G$. The size of a smallest decycling set of $G$ is called the decycling number of $G$. Determining the decycling number of a graph $G$ is NP-hard, even if $G$ is bipartite. We describe a tabu search procedure that generates decycling sets of small size for arbitrary bipartite graphs. Tests on challenging families of graphs show that the proposed algorithm improves many best-known solutions, thus closing or narrowing the gap to the best-known lower bounds.
DOI : 10.7155/jgaa.00567
Keywords: decycling number, feedback vertex set, induced forest, bipartite graph, tabu search 
@article{JGAA_2021_25_1_a20,
     author = {Alain Hertz},
     title = {Decycling bipartite graphs},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {461--480},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00567},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00567/}
}
TY  - JOUR
AU  - Alain Hertz
TI  - Decycling bipartite graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 461
EP  - 480
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00567/
DO  - 10.7155/jgaa.00567
LA  - en
ID  - JGAA_2021_25_1_a20
ER  - 
%0 Journal Article
%A Alain Hertz
%T Decycling bipartite graphs
%J Journal of Graph Algorithms and Applications
%D 2021
%P 461-480
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00567/
%R 10.7155/jgaa.00567
%G en
%F JGAA_2021_25_1_a20
Alain Hertz. Decycling bipartite graphs. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 461-480. doi : 10.7155/jgaa.00567. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00567/

Cité par Sources :