Abstract | ||
---|---|---|
We deal with different algorithmic questions regarding properly arc-colored s-t paths, trails and circuits in arc-colored digraphs Given an arc-colored digraph Dc with c≥2 colors, we show that the problem of maximizing the number of arc disjoint properly arc-colored s-t trails can be solved in polynomial time Surprisingly, we prove that the determination of one properly arc-colored s-t path is NP-complete even for planar digraphs containing no properly arc-colored circuits and c=Ω(n), where n denotes the number of vertices in Dc 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, even if c=2 As a consequence, we solve a weak version of an open problem posed in Gutin et al. [17]. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1007/978-3-642-13562-0_21 | TAMC |
Keywords | Field | DocType |
arc-colored s-t,open problem,arc-colored tournament,arc disjoint,planar digraph,arc-colored digraph,arc-colored s-t path,arc-colored circuit,hamiltonian s-t path,arc-colored digraph dc,np completeness,polynomial time | Discrete mathematics,Combinatorics,Tournament,Open problem,Arc (geometry),Disjoint sets,Vertex (geometry),Hamiltonian (quantum mechanics),Time complexity,Digraph,Mathematics | Conference |
Volume | ISSN | ISBN |
6108 | 0302-9743 | 3-642-13561-7 |
Citations | PageRank | References |
3 | 0.43 | 17 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Laurent Gourvès | 1 | 241 | 30.97 |
Adria Lyra | 2 | 33 | 3.02 |
Carlos Martinhon | 3 | 25 | 1.78 |
Jérôme Monnot | 4 | 512 | 55.74 |