1.
public boolean twoColor(int i, int [] label)
{
int n = vertices();
// do a breadth first search in the component
ArrayQueue q = new ArrayQueue(10);
label[i] = 1;
q.put(new Integer(i));
while (!q.isEmpty())
{
// remove a labeled vertex from the queue
int w = ((Integer) q.remove()).intValue();
// mark all unreached vertices adjacent from w
Iterator iw = iterator(w);
while (iw.hasNext())
{// visit an adjacent vertex of w
int u = ((EdgeNode) iw.next()).vertex;
if (label[u] == 0)
{// u is an unreached vertex
q.put(new Integer(u));
label[u] = 3 - label[w]; // assign u the other label
}
else
// u already labeled
if (label[u] == label[w])
// both ends of edge assigned same label
return false;
}
}
// labeling successful
return true;
}
while loop
takes O(degree of w) time for each
w that is examined. So the complexity
is linear in the number of vertices in the component
and the sum of their degrees. This latter sum is twice the number of edges
in the component.
Therefore, the complexity is
O(number of vertices in the component + number of
edges in the component).
Let currentTime = 0.
Let n be the number of jobs.
Let J be the set of remaining jobs.
while (J is not empty)
{
remove from J all jobs whose deadline is <= currentTime + jobLength;
from the jobs (if any) that remain, select a minimum length job
whose release time is <= currentTime;
if (such a job exists)
{
the selected job will be processed sucessfully from currentTime to
currentTime + jobLength;
curentTime += jobLength;
remove the selected job from J;
}
}
(10, 0, 10) (3, 1, 4) (2, 4, 6)
1 when
currentTime = 0, and is then unable
to select any other job.
The optimal selection is jobs 2 and 3.
w(n,j) = infinity, j < C(n,1)
w(n,j) = W(n,1), C(n,1) <= j < C(n,2)
w(n,j) = W(n,2),
C(n,2) <= j <= c
w(i,j) = infinity, j < C(i,1)
w(i,j) = W(i,1) + w(i+1, j-C(i,1)), C(i,1) <= j
< C(i,2)
w(i,j) = min{W(i,1) + w(i+1, j-C(i,1)),
W(i,2) + w(i+1, j-C(i,2))},
C(i,2) <= j <= c
ws as follows:
w(n,j) for 0 <= j <= c
using the equation for w(n,j) that is given above.
This takes O(c) time.
w(i,j) for
i = n-1, n-2, ... 1, in that order,
using the equation for w(i,j)
that is given above. For each i,
compute w(i,j) for
0 <= j <= c (this can be done in any
order).
It takes O(cn) time to compute all of these
w(i,j) values.
w(1,c) gives the least weight machine
that can be constructed at a cost that does not exceed
c.
The supplier for each component is determined by using a traceback procedure
for w(1,c).
Assume that w(1,c) != infinity. Therefore, it is possible
to build the machine at a cost that does not exceed c.
w(i,j) is recursive.
When i = n, there are two cases to consider.
If w(n,j) = W(n,1), get component
n from supplier 1;
otherwise, w(n,j) = W(n,2) and we must get component
n from supplier 2.
i < n, there are also two cases to consider.
If
w(i,j) = W(i,1) + w(i+1, j-C(i,1)),
then get component i from supplier
1
and do a traceback for w(i+1, j-W(i,1))
to determine the suppliers for the remaining components;
otherwise,
w(i,j) = W(i,2) + w(i+1, j-C(i,2)),
and we must get component i from supplier
2
and do a traceback for w(i+1, j-W(i,2))
to determine the suppliers for the remaining components.
S
of the vertices of the graph that satisfies the stated property.
A solution may be described by the array x[]
where x[i] is 1
if vertex i
is in the subset S and 0 if it is not in this subset.