Parameterized Traveling Salesman Problem: Beating the Average

DOI10.1137/140980946zbMath1329.05179arXiv1408.0531OpenAlexW2254574817MaRDI QIDQ5743554

Gregory Gutin, Viresh Patel

Publication date: 5 February 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.0531

zbMATH Keywords

traveling salesman problemfixed-parameter tractablebelow average

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15) Eulerian and Hamiltonian graphs (05C45)

Related Items (6)

Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Detours in directed graphs ⋮ Going Far from Degeneracy ⋮ Unnamed Item ⋮ Turán’s Theorem Through Algorithmic Lens ⋮ Approximating long cycle above Dirac's guarantee

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Solving MAX-\(r\)-SAT above a tight lower bound
• Parameterizing above or below guaranteed values
• Geometric algorithms and combinatorial optimization
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• A domination algorithm for {0,1}-instances of the travelling salesman problem
• Max-Cut Parameterized above the Edwards-Erdős Bound
• Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
• Probability and Computing
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Parameterized Traveling Salesman Problem: Beating the Average