Domination Lab

University of Bojnord

Draw a graph, pick a problem, and see right away where its definition holds and where it fails. Graphs can have up to 150 vertices. For small graphs you also get the exact answer, and the algorithms can be followed one step at a time. Domatic partitions and unit disk graphs are included too.

Quick start
  1. Start by choosing a problem in step 1, for example Dominating set.
  2. Tap vertices to build the set S. Wherever the definition fails, the vertex or edge turns red.
  3. The Analyze tab gives the optimum, a table of parameters and the domatic partition.
  4. The Algorithms tab lets you follow an algorithm for the chosen problem one step at a time.
  5. The Graph tab has example graphs, or you can draw your own. Under the canvas you can save the result as a PDF or an Ipe drawing.

1. Choose a problem

2. Build, analyze and run algorithms

in Scondition satisfiedviolated
Load Ipe file

If Load Ipe file does nothing in your viewer, paste the file’s text into the box under “Import or export” at the bottom of the page, or open the page in a normal browser. Dropping an .ipe file onto the page also works.

In unit disk mode two vertices are adjacent when their distance is at most the radius. Drag the vertices and watch the graph change.

3. Algorithms: explanation, pseudocode and references

The idea, pseudocode, analysis and references of every algorithm in this lab are on a separate page. The formulas are typeset with LaTeX, and there are PDF versions in English and Persian.

Open the algorithms page
Import or export an edge list

Write n=6 and the edges, for example 1-2, 2-3, 3-6, then press Apply. For Ipe drawings use the Save as Ipe and Load Ipe file buttons under the graph.

Or paste the text of an .ipe file here:

Ipe text of the current graph (to copy):