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

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

Displaying similar documents to “On the lower bound of the spectral norm of symmetric random matrices with independent entries.”

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...