We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Finding paths in graphs avoiding forbidden transitions.

Szeider, S. (2003) 'Finding paths in graphs avoiding forbidden transitions.', Discrete applied mathematics., 126 (2-3). pp. 261-273.


Let v be a vertex of a graph G; a transition graph T(v) of v is a graph whose vertices are the edges incident with v. We consider graphs G with prescribed transition systems T={T(v) | vV(G)}. A path P in G is called T-compatible, if each pair uv,vw of consecutive edges of P form an edge in T(v). Let be a given class of graphs (closed under isomorphism). We study the computational complexity of finding T-compatible paths between two given vertices of a graph for a specified transition system . Our main result is that a dichotomy holds (subject to the assumption P≠NP). That is, for a considered class , the problem is either (1) NP-complete, or (2) it can be solved in linear time. We give a criterion—based on vertex induced subgraphs—which decides whether (1) or (2) holds for any given class.

Item Type:Article
Keywords:Compatible path, Transition, Edge-colored graph, Forbidden pairs, NP-Completeness, Linear time algorithm.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Record Created:14 Oct 2008
Last Modified:03 Oct 2016 10:59

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library