Loading...
Please wait, while we are loading the content...
Similar Documents
Finding paths in graphs avoiding prescribed transitions
| Content Provider | Semantic Scholar |
|---|---|
| Author | Szeider, Stefan |
| Copyright Year | 2000 |
| Abstract | 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) | v ∈ V (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 A 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 T ⊆ A. Our main result is that a dichotomy holds (subject to the assumption P 6= NP). That is, for a considered class A, the problem is either (1) NP-complete, or (2) it can be solved in polynomial time. We give a criterion—based on vertex induced subgraphs—which decides whether (1) or (2) holds for any given class A. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://goedel.dismat.oeaw.ac.at/papers/compatible.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
