mtmt
The Hungarian Scientific Bibliography
XML
JSON
Public search
Magyarul
An Efficient Algorithm to Compute the Toughness in Graphs with Bounded Treewidth
Katona, Gyula Y. ✉ [Katona, Gyula Y. (gráfelmélet), author] Department of Computer Science and Information ... (BUTE / FEEI); HUN-REN-ELTE Numerical Analysis and Large Netwo... (ELTE / ELU FoS / IM)
;
Khan, Humara [Khan, Humara (Graph Theory), author] Department of Computer Science and Information ... (BUTE / FEEI)
English Article (Journal Article) Scientific
Published:
GRAPHS AND COMBINATORICS 0911-0119 1435-5914
40
(5)
Paper: 100
, 11 p.
2024
SJR Scopus - Discrete Mathematics and Combinatorics: Q2
Identifiers
MTMT: 35192732
DOI:
10.1007/s00373-024-02828-y
WoS:
001295892100002
Scopus:
85201724028
Subjects:
Mathematics
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.
Citing (2)
Citation styles:
IEEE
ACM
APA
Chicago
Harvard
CSL
Copy
Print
2025-04-26 00:07
×
Export list as bibliography
Citation styles:
IEEE
ACM
APA
Chicago
Harvard
Print
Copy