Retour

G-2020-43

Decycling bipartite graphs

référence BibTeX

Let G=(V,E) be a graph and let SV be a subset of its vertices. If the subgraph of G induced by VS 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.

, 20 pages

Axe de recherche

Publication

Journal of Graph Algorithms and Applications, 25(1), 461–480, 2021 référence BibTeX