scientific article; zbMATH DE number 2102640

zbMath1045.05082MaRDI QIDQ4817463

E. Kh. Gimadi, Natalie M. Korkishko, Alexei E. Baburin

Publication date: 23 September 2004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

NP-completenessNP-hardnessundirected graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Nonnumerical algorithms (68W05) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items (7)

A polynomial algorithm with asymptotic ratio $2/3$ for the asymmetric maximization version of the $m$-PSP ⋮ Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP ⋮ An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution ⋮ Combinatorial algorithms with performance guarantees for finding several Hamiltonian circuits in a complete directed weighted graph ⋮ A 2-Approximation Algorithm for the Metric 2-Peripatetic Salesman Problem ⋮ A Polynomial 3/5-Approximate Algorithm for the Asymmetric Maximization Version of the 3-PSP ⋮ Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2

This page was built for publication: