An efficient algorithm to compute the toughness in graphs with bounded treewidth

DOI10.1007/S00373-024-02828-YMaRDI QIDQ6616440zbMATH OpenFDO

Authors Gyula Y. Katona, Humara Khan

Publication date 9 October 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00373-024-02828-Y

zbMATH Keywords

fixed-parameter tractabletougnesstreewidth

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• The toughness of split graphs
• Minimal toughness in special graph classes
• A note on the approximability of the toughness of graphs

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity of Finding Embeddings in a k-Tree
• Computations by fly-automata beyond monadic second-order logic
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Hamiltonian results inK1,3-free graphs
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 734468 (Why is no real title available?)
• scientific article; zbMATH DE number 1472146 (Why is no real title available?)
• scientific article; zbMATH DE number 7075896 (Why is no real title available?)
• Improved bounds on Bell numbers and on moments of sums of random variables
• On the complexity of recognizing tough graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Parameterized algorithms
• Recognizing tough graphs is NP-hard
• The complexity of recognizing tough cubic graphs
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• The toughness of split graphs
• Tough graphs and Hamiltonian circuits.
• Toughness, hamiltonicity and split graphs

This page was built for publication: An efficient algorithm to compute the toughness in graphs with bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6616440)