An Efficient Algorithm to Compute the Toughness in Graphs with Bounded Treewidth

Katona, Gyula Y. ✉ [Katona, Gyula Y. (gráfelmélet), szerző] Számítástudományi és Információelméleti Tanszék (BME / VIK); Khan, Humara [Khan, Humara (Graph Theory), szerző] Számítástudományi és Információelméleti Tanszék (BME / VIK)

Angol nyelvű Szakcikk (Folyóiratcikk) Tudományos
Megjelent: GRAPHS AND COMBINATORICS 0911-0119 1435-5914 40 (5) Paper: 100 , 11 p. 2024
  • SJR Scopus - Discrete Mathematics and Combinatorics: Q2
Azonosítók
Szakterületek:
  • Matematika
Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components. The toughness of a graph is the largest t for which the graph is t-tough. We prove that toughness is fixed-parameter tractable parameterized with the treewidth. More precisely, we give an algorithm to compute the toughness of a graph G with running time O(|V(G)|3·tw(G)2tw(G)) where tw(G) is the treewidth. If the treewidth is bounded by a constant, then this is a polynomial algorithm. © The Author(s) 2024.
Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
2024-11-04 13:22