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

DOI10.1007/S00373-024-02828-YzbMATH Open1548.05189MaRDI QIDQ6616440

Gyula Y. Katona, Humara Khan

Publication date: 9 October 2024

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

zbMATH Keywords

treewidthfixed-parameter tractabletougness

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognizing tough graphs is NP-hard
• Graph minors. I. Excluding a forest
• On the complexity of recognizing tough graphs
• The complexity of recognizing tough cubic graphs
• The toughness of split graphs
• Toughness, hamiltonicity and split graphs
• Tough graphs and Hamiltonian circuits.
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Hamiltonian results inK1,3-free graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• On Toughness and Hamiltonicity of 2K₂‐Free Graphs
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computations by fly-automata beyond monadic second-order logic

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)