dsdp-color man page

dsdp-color — Find an approximate coloring of a graph


dsdp-color [Options] GRAPH_FILE


The dsdp-color program reads a graph from a file, formulates the SDP relaxation of the k-coloring problem, solves the problem using the DSDP library, and applies a randomized algorithm to generate an approximate solution.

A positive semidefinite relaxation of the graph k-coloring problem can be rewritten as
Find X>=0
such that X_ij <= 1 - 1/(k-1) for all edges (i,j).


-dloginfo N
Set the logging level (default 0). More information is printed for higher numbers.
-params FILE
Read DSDP parameters from FILE
Print a help message

File Format

The input file should be in the following format:

n m
r1 c1 [w1]

im jm [wm]

where n is the number of nodes, and m is the number of edges. Each r/c pair or r/c/w triple describes one edge, where r is the row, c is the column, and w is the weight. The weight defaults to 0.0. The weight is not used, except that a weight of 0.0 means to ignore the edge.

See Also

dsdp5(1), dsdp-maxcut(1), dsdp-stable(1), dsdp-theta(1)

Referenced By

dsdp5(1), dsdp-maxcut(1), dsdp-stable(1), dsdp-theta(1).

5.8 DSDP User Commands