Computer-Aided Program Development Institute of Computer Science Faculty of Engineering, Christian-Albrechts-University of Kiel

{************************************************************
 Computation of a sequence of vectors approximating a mini-
 mum colouring of a simple graph. The approximation algo-
 rithm can be found in Emden-Weinert et al., p. 130
************************************************************}

ColourApprox(R)
  DECL C, p, c
  BEG  p = point(Ln1(R));
       C = p * p^;
       WHILE -universal(dom(C)) DO
         p = point(-dom(C));
         c = point(-(C^ * R * p));
         C = C | p * c^
         OD
       RETURN C * inj(ran(C))^
  END.

{************************************************************
 Approximation algorithm for a minimum vertex cover of an
 undirected and loop-free graph following the book of Cor-
 men, Leiserson and Rivest, p. 967. The algorithm has ra-
 tio bound 2
************************************************************}

VertexCovApprox(R)
  DECL E, c, e
  BEG  c = On1(R);
       E = R;
       WHILE -empty(E) DO
         e = edge(E);
         c = c | dom(e);
         E = E & -(e*L(e) & R) & -(L(e)*e & R)
         OD
       RETURN c
  END.

{************************************************************
 Approximation algorithm for a minimum edge cover of a con-
 nected undirected and loopfree graph following the book of 
 Cormen, Leiserson and Rivest, p. 975. There, the algorithm 
 is formulated for the set covering problem. The algorithm
 has a ratio bound 3/2
************************************************************}

EdgeCovApprox(R)
  DECL C, K, u, e
  BEG  u = Ln1(R);
       C = O(R);
       WHILE -empty(u) DO
         K = u * u^ & R;
         IF -empty(K) THEN e = edge(K)
                      ELSE K = (u*L(u)^ | L(u)*u^) & R;
                           e = edge(K) FI;
         u = u & -dom(e);
         C = C | e 
         OD
       RETURN C
  END.

{************************************************************
 Approximation algorithm for a maximum cut of an undirect-
 ed and loopfree graph with ratio bound 2
************************************************************}

MaxCut(R)
  DECL c1, c2, v, p
  BEG  v = Ln1(R);
       c1 = On1(R);
       c2 = On1(R);
       WHILE -empty(v) DO
         p = point(v);
         IF cardlt(R*p&c1,R*p&c2) THEN c1 = c1 | p
                                  ELSE c2 = c2 | p FI;
         v = v & -p 
         OD
       RETURN c1
  END.