Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different c...Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.展开更多
We deal with the problem of sharing vehicles by individuals with similar itineraries which is to find the minimum number of drivers, each of which has a vehicle capacity and a detour to realize all trips. Recently, Gu...We deal with the problem of sharing vehicles by individuals with similar itineraries which is to find the minimum number of drivers, each of which has a vehicle capacity and a detour to realize all trips. Recently, Gu et al. showed that the problem is NP-hard even for star graphs restricted with unique destination, and gave a polynomial-time algorithm to solve the problem for paths restricted with unique destination and zero detour. In this paper we will give a dynamic programming algorithm to solve the problem in polynomial time for trees restricted with unique destination and zero detour. In our best knowledge it is a first polynomial-time algorithm for trees.展开更多
Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we a...Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we assume that every job is non-preemptive. Let C={1,2,...} be a color set. A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets. Such a multicoloring is called a non-preemptive scheduling. The cost non-preemptive scheduling problem is to find an optimal multicoloring of G.展开更多
文摘Let C be a set of colors, and let ?be an integer cost assigned to a color c in C. An edge-coloring of a graph ?is assigning a color in C to each edge ?so that any two edges having end-vertex in common have different colors. The cost ?of an edge-coloring f of G is the sum of costs ?of colors ?assigned to all edges e in G. An edge-coloring f of G is optimal if ?is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge- ??coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.
文摘We deal with the problem of sharing vehicles by individuals with similar itineraries which is to find the minimum number of drivers, each of which has a vehicle capacity and a detour to realize all trips. Recently, Gu et al. showed that the problem is NP-hard even for star graphs restricted with unique destination, and gave a polynomial-time algorithm to solve the problem for paths restricted with unique destination and zero detour. In this paper we will give a dynamic programming algorithm to solve the problem in polynomial time for trees restricted with unique destination and zero detour. In our best knowledge it is a first polynomial-time algorithm for trees.
文摘Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we assume that every job is non-preemptive. Let C={1,2,...} be a color set. A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets. Such a multicoloring is called a non-preemptive scheduling. The cost non-preemptive scheduling problem is to find an optimal multicoloring of G.
