PROGRAM DYNAMIC
      IMPLICIT INTEGER(A-Z)
      DOUBLE PRECISION TIMEA,TIMEB,TIMTOT,A(50,50),EPS
      REAL S1
      INTEGER X(50),Q(50),D(50,50,50),S(50)
C
C #################################################################
C  5/2005: Finds a maximum cardinality subset of objects with
C          perfect anti-Robinson structure.
C #################################################################
C
      OPEN(1,FILE='AMAT.DAT')          ! Dissimilarity matrix
      OPEN(2,FILE='SEQ.OUT')           ! Output file
      EPS = 1.0d-07
      READ(1,*) N                      ! Read number of objects
      WRITE(*,*) 'TYPE 1 FOR HALF MATRIX OR TYPE 2 FOR FULL MATRIX'
      READ(*,*) ITYPE
      IF(ITYPE.EQ.2) THEN
        READ(1,*) ((A(I,J),J=1,N),I=1,N)
      ELSE
        DO J = 2,N
          READ(1,*) (A(I,J),I=1,J-1)
        END DO
        DO J = 2,N
          DO I = 1,J-1
            A(J,I) = A(I,J)
          END DO
        END DO
      END IF
      CALL GETTIM (IHR, IMIN, ISEC, I100)
      CALL GETDAT (IYR, IMON, IDAY)
      TIMEA=DFLOAT(86400*IDAY+3600*IHR+60*IMIN+ISEC)+DFLOAT(I100)/100.
      DO I = 1,N
        A(I,I) = 0.0D0
      END DO
C
      DO 848 I = 1,N
        DO 849 J = 1,N
          IF(I.EQ.J) GO TO 849
          DO 850 K = 1,N
            IF(I.EQ.K.OR.J.EQ.K) GO TO 850
            IF(A(I,K).GE.A(I,J).AND.A(I,K).GE.A(J,K)) D(I,J,K)=1
 850      CONTINUE
 849    CONTINUE
 848  CONTINUE
C
C
      Z = 0
      DO I = 1,N
        Q(I) = 0
      END DO
C
      M=1
      Q(M)=1
      S(1)=1
      DO K = 2,N
        Q(K)=0
      END DO
C
  1   M = M + 1
C
  2   Q(M)=Q(M)+1
C
      IF(S(Q(M)).EQ.1) GO TO 2               ! REDUNDANCY
      IF(M.EQ.1.AND.Q(M).GT.N) GO TO 9       ! TERMINATE
      IF(M.GT.1.AND.Q(M).GT.N) GO TO 7       ! GO TO RETRACTION
      S(Q(M))=1
      R3 = Q(M)
      DO I = 1,M-2
        R1 = Q(I)
        DO J = I+1,M-1
          R2 = Q(J)
          IF(D(R1,R2,R3).EQ.0) THEN
            S(Q(M))=0
            GO TO 2
          END IF
        END DO
      END DO
      IF(M.GT.Z) THEN
        Z = M
        DO I = 1,N
          X(I)=Q(I)
        END DO
      END IF
      GO TO 1
C
   7  S(Q(M))=0
      Q(M)=0
      M=M-1
      S(Q(M))=0
      GO TO 2
   9  CALL GETTIM (IHR, IMIN, ISEC, I100)
      CALL GETDAT (IYR, IMON, IDAY)
      TIMEB=DFLOAT(86400*IDAY+3600*IHR+60*IMIN+ISEC)+DFLOAT(I100)/100.
      TIMTOT=TIMEB-TIMEA
      WRITE(*,69) Z
      WRITE(2,69) Z
      WRITE(*,79) TIMTOT
      WRITE(2,79) TIMTOT
      WRITE(2,70) (X(I),I=1,N)
 69   FORMAT(' MAXIMUM SUBSET SIZE WITH PERFECT AR STRUCTURE ',I7)
 79   FORMAT(' CPU TIME ',F8.2)
 70   FORMAT(30I3)
C
      END