1DSDP-COLOR(1)                    User Commands                   DSDP-COLOR(1)
2
3
4

NAME

6       dsdp-color - Find an approximate coloring of a graph
7

SYNOPSIS

9       dsdp-color [OPTIONS] GRAPH_FILE
10

DESCRIPTION

12       The  dsdp-color  program  reads a graph from a file, formulates the SDP
13       relaxation of the k-coloring problem, solves the problem using the DSDP
14       library,  and applies a randomized algorithm to generate an approximate
15       solution.
16
17       A positive semidefinite relaxation of the graph k-coloring problem  can
18       be rewritten as
19          Find       X>=0
20          such that  X_ij <= 1 - 1/(k-1) for all edges (i,j).
21

OPTIONS

23       -dloginfo N
24              Set  the logging level (default 0).  More information is printed
25              for higher numbers.
26
27       -params FILE
28              Read DSDP parameters from FILE
29
30       -help  Print a help message
31

FILE FORMAT

33       The input file should be in the following format:
34              n m
35              r1 c1 [w1]
36              …
37              im jm [wm]
38       where n is the number of nodes, and m is the number of edges.  Each r/c
39       pair  or  r/c/w triple describes one edge, where r is the row, c is the
40       column, and w is the weight.  The weight defaults to 0.0.   The  weight
41       is not used, except that a weight of 0.0 means to ignore the edge.
42

SEE ALSO

44       dsdp5(1), dsdp-maxcut(1), dsdp-stable(1), dsdp-theta(1)
45
46
47
48DSDP                                  5.8                        DSDP-COLOR(1)