Решатель - это ява-программа
для нахождения наибольшего независимого множества
или наибольшей клики в неориентированном графе

Аннотация

Решатель - это ява-программа для точного нахождения наибольшего независимого множества или наибольшей клики в произвольном неориентированном графе. Он использует полиномиально-временной алгоритм, разработанный Анатолием Плотниковым. Решатель разработан с целью испытания справедливости гипотезы Анатолия Плотникова о свойствах вершинно-насыщенных орграфов и исследования алгоритма.

Решатель может быть использован на любой операционной системе.

Свойства

Главные свойства Решателя включают:

• поддержку неориентированных графов;
• нахождение наибольшего независимого множества;
• нахождение наибольшей клики;
• определение времени решения.

Инструкция пользователю

Программа работает различным образом. Просто используйте ява-файл, печатая

java -jar mmisfinder.jar <'inputfile'> [-out <'outputfile'>] [-progress] [-time] [-dVS] [-dMIS] [-dCutting] [-dPart] [-dLayer],

где взамен <'inputfile'> вы должны вставить имя входного файла (или пути) входного графа. Если входной файл имеет файловое имя с расширением " .mis", то программа находит наибольшее независимое множество. Если входной файл имеет файловое имя с расширением ".clq", то программа находит наибольшую клику. Входной файл должен использовать формат DIMACS (смотри, например,
ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique
и
http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm).

Добавляя опцию "-out <'outputfile'>", вы можете указывать имя файла с решением. Если вы не указываете имя файла с решением, то будет использовано имя входного файла с расширением ".sol".

Добавляя опцию "-progress", вы можете видеть краткую информацию о том, что алгоритм делает в данный момент. Это интересно только при решении громоздких примеров графов.

Добавляя опцию "-time", вы можете видеть время решения в sol-файле.

Добавляя опцию "-dVS", вы можете видеть информацию о том, как программа создает вершинно-насыщенные графы.

Добавляя опцию "-dMIS", вы можете видеть информацию о главном алгоритме.

Добавляя опцию "-dCutting", вы можете видеть информацию о выполнении операции "сечения".

Добавляя опцию "-dPart", вы можете видеть информацию о вычислении цепного разбиения.

Добавляя опцию "-dLayer", вы можете видеть информацию о том, как открываются слои орграфа.

Использование терминологии теории графов смотри в статье Анатолия Плотникова.

Загрузка

Текущая версия программы реализована в 2008.

Вы можете загрузить программу здесь:

Если вы имеете любые проблемы в использовании этой программы, чувствуете себя свободно спросить о них у ее автора.

Вы должны сослаться на эту страницу, если вы используете Решатель в вашей научной работе. Если вы хотите отпечатать копию программы, пожалуйста, пишите Томасу Карбе ( Thomas Karbe) (электронный адрес смотри ниже в части "Автор").

Лицензия

Решатель лицензирован под GNU General Public License. По существу, вы можете использовать Решатель с любой целью, при условии, что любые программы или их модификации, которые вы пишите и распространяете также лицензированы под GNU GPL.

Абсолютно никаких гарантий или обязательств не делается относительно пригодности, правильности или других аспектов этой программы.

Copyright © 2008 Thomas Karbe, Anatoly Plotnikov.

Автор

Решатель был написан Томасом Карбе (Thomas Karbe), Берлинский технический университет , karbePcs.tu-berlin.de (P=@)).

Для исправления ошибок, обратной связи относительно Решателя, пожалуйста, пишите автору.