Directed in-out graphs of optimal size

Authors David G. Glynn, Michael Haythorpe, Asghar Moeini

Publication date 13 February 2019

Full work available at URL https://arxiv.org/abs/1702.03075, http://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p405.pdf

\(k\)-in-out graphs traveling salesman problem

Directed graphs (digraphs), tournaments (05C20) Programming involving graphs or networks (90C35)

Abstract: We discuss the recently introduced concept of k-in-out graphs, and provide a construction for k-in-out graphs for any positive integer k. We derive a lower bound for the number of vertices of a k-in-out graph for any positive integer k, and demonstrate that our construction meets this bound in all cases. For even k, we also prove our construction is optimal with respect to the number of edges, and results in a planar graph. Among the possible uses of in-out graphs, they can convert the generalized traveling salesman problem to the asymmetric traveling salesman problem, avoiding the "big M" issue present in most other conversions. We give constraints satisfied by all in-out graphs to assist cutting-plane algorithms in solving instances of traveling salesman problem which contain in-out graphs.

Recommendations

Cites work

Cited in

(2)

Describes a project that uses

Uses Software

This page was built for publication: Directed in-out graphs of optimal size

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