mtmt
Magyar Tudományos Művek Tára
XML
JSON
Átlépés a keresőbe
In English
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
MTMT: 35192732
DOI:
10.1007/s00373-024-02828-y
WoS:
001295892100002
Scopus:
85201724028
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.
Idézett közlemények (2)
Hivatkozás stílusok:
IEEE
ACM
APA
Chicago
Harvard
CSL
Másolás
Nyomtatás
2024-11-04 13:22
×
Lista exportálása irodalomjegyzékként
Hivatkozás stílusok:
IEEE
ACM
APA
Chicago
Harvard
Nyomtatás
Másolás