The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “The Orderly Colored Longest Path Problem – a survey of applications and new algorithms”

Paths through fixed vertices in edge-colored graphs

W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, Zs. Tuza (1994)

Mathématiques et Sciences Humaines

Similarity:

We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length...

On k-Path Pancyclic Graphs

Zhenming Bi, Ping Zhang (2015)

Discussiones Mathematicae Graph Theory

Similarity:

For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G...

More on the complexity of cover graphs

Jaroslav Nešetřil, Vojtěch Rödl (1995)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.