On Minimum Connecting Transition Sets in Graphs

DOI10.1007/978-3-030-00256-5_4MaRDI QIDQ6304514arXivFDO

Authors Thomas Bellitto, Benjamin Bergougnoux

Publication date 23 July 2018

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-00256-5_4

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

arXiv classification

cs.DMcs.DSmath.CO

Abstract: A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.

This page was built for publication: On Minimum Connecting Transition Sets in Graphs

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