Name
Abstract | ||
|---|---|---|
We deal with different algorithmic questions regarding properly arc-colored s-t trails, paths and circuits in arc-colored digraphs. Given an arc-colored digraph D^c with c=2 colors, we show that the problem of determining the maximum number of arc disjoint properly arc-colored s-t trails can be solved in polynomial time. Surprisingly, we prove that the determination of a properly arc-colored s-t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c=@W(n), where n denotes the number of vertices in D^c. If the digraph is an arc-colored tournament, we show that deciding whether it contains a properly arc-colored circuit passing through a given vertex x (resp., properly arc-colored Hamiltonian s-t path) is NP-complete for c=2. As a consequence, we solve a weak version of an open problem posed in Gutin et al. (1998) [23], whose objective is to determine whether a 2-arc-colored tournament contains a properly arc-colored circuit. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.dam.2012.10.025 | Discrete Applied Mathematics |
Keywords | Field | DocType |
2-arc-colored tournament,arc-colored s-t,open problem,arc-colored tournament,planar digraph,arc-colored digraph,arc-colored s-t path,maximum number,arc-colored circuit,hamiltonian s-t path,np completeness | Discrete mathematics,Tournament,Combinatorics,Open problem,Disjoint sets,Vertex (geometry),Hamiltonian (quantum mechanics),Electronic circuit,Time complexity,Mathematics,Digraph | Journal |
Volume | Issue | ISSN |
161 | 6 | 0166-218X |
Citations | PageRank | References |
5 | 0.47 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Gourvès | 1 | 241 | 30.97 |
| Adria Lyra | 2 | 33 | 3.02 |
| Carlos A. Martinhon | 3 | 8 | 2.25 |
| Jérôme Monnot | 4 | 512 | 55.74 |