Directed in-out graphs of optimal size

David Glynn, Michael Haythorpe, Asghar Moeini

Research output: Contribution to journalArticle

2 Downloads (Pure)

Abstract

We discuss the recently introduced concept of k-in-out graphs, and provide a construction fork-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.
Original languageEnglish
Pages (from-to)405-420
Number of pages16
JournalAustralasian Journal of Combinatorics, the
Volume72
Issue number2
Publication statusPublished - 2018

Bibliographical note

©The author(s). Released under the CC BY 4.0 International License

Keywords

  • k-in-out graphs
  • traveling salesman problem
  • cutting-plane algorithms

Fingerprint Dive into the research topics of 'Directed in-out graphs of optimal size'. Together they form a unique fingerprint.

  • Cite this