G-2020-43
Decycling bipartite graphs
référence BibTeX
Let G=(V,E)
be a graph and let S⊆V
be a subset of its vertices. If the subgraph of G
induced by V∖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 procedure that generates an upper bound on the decycling number of arbitrary bipartite graphs. Tests on challenging families of graphs show that the proposed algorithm improves many best-known upper bounds, thus closing or narrowing the gap to the best-known lower bounds.
Paru en juillet 2020 , 20 pages
Axe de recherche
Publication
sept. 2021
Journal of Graph Algorithms and Applications, 25(1), 461–480, 2021
référence BibTeX