Name
Abstract | ||
|---|---|---|
. Motivated by the problem of efficient routing in all-opticalnetworks, we study a constrained version of the bipartite edge coloringproblem. We show that if the edges adjacent to a pair of opposite verticesof an L-regular bipartite graph are already colored with ffL differentcolors, then the rest of the edges can be colored using at most (1+ff=2)Lcolors. We also show that this bound is tight by constructing instancesin which (1 + ff=2)L colors are indeed necessary. We also obtain tight... |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/3-540-63165-8_205 | ICALP |
Keywords | Field | DocType |
wavelength routing,constrained bipartite edge coloring,bipartite graph,edge coloring | Edge coloring,Complete coloring,Discrete mathematics,Combinatorics,Colored,Fractional coloring,Vertex (geometry),Bipartite graph,Greedy algorithm,Greedy coloring,Mathematics,Distributed computing | Conference |
Volume | ISSN | ISBN |
1256 | 0302-9743 | 3-540-63165-8 |
Citations | PageRank | References |
29 | 2.53 | 6 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Kaklamanis | 1 | 855 | 85.90 |
| Pino Persiano | 2 | 277 | 21.06 |
| Thomas Erlebach | 3 | 1233 | 102.74 |
| Klaus Jansen | 4 | 789 | 82.68 |