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

NAME

6       dsdp-theta - Compute the Lovasz Theta number of a graph
7

SYNOPSIS

9       dsdp-theta [OPTIONS] GRAPH_FILE
10

DESCRIPTION

12       The  dsdp-theta  program  uses  the  DSDP library to compute the Lovasz
13       Theta number of an input graph.  This number is an upper bound for  the
14       maximum  clique  of a graph, a lower bound for the minimal graph color‐
15       ing, and serves as a bound for several other combinatorial graph  prob‐
16       lems.  The number is the solution to a semidefinite program.
17
18       The  input  file should be the complement of the graph.  This file also
19       demonstrates the use of customized data matrices in DSDP.
20

OPTIONS

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

FILE FORMAT

32       The input file should be in the following format:
33              n m
34              r1 c1 [w1]
35              …
36              im jm [wm]
37       where n is the number of nodes, and m is the number of edges.  Each r/c
38       pair or r/c/w triple describes one edge, where r is the row, c  is  the
39       column, and w is the weight.  The weight is ignored, if present.
40

SEE ALSO

42       dsdp-color(1), dsdp5(1), dsdp-maxcut(1), dsdp-stable(1)
43
44
45
46DSDP                                  5.8                        DSDP-THETA(1)