Модели и алгоритмы верификации топологии печатного монтажа тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Лузин, Михаил Сергеевич

• Лузин, Михаил Сергеевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Лузин, Михаил Сергеевич

ВВЕДЕНИЕ.

I. УСТАНОВЛЕНИЕ ИЗОМОРФНОСТИ РАЗЛИЧНЫХ

ОПИСАНИЙ

1.1. Изоморфность мультиграфов.

1.2. Избыточность мультиграфового представления принципиальной схемы.

1.3. Выводы

II. РАЗРАБОТКА АЛГОРИТМА ОПРЕДЕЛЕНИЯ ИЗОМОРФНОСТИ ОПИСАНИЙ ТОПОЛОГИИ

И ПРИНЦИПИАЛЬНОЙ СХЕМЫ.

2.1. Изоморфность гиперграфов.

2.2. Инварианты матрицы инцидентности гиперграфа

2.3. Компактное представление гиперграфа.

2.4. Алгоритм определения изоморфности гиперграфов

2.5. Выводы

III. ИСПОЛЬЗОВАНИЕ ФУНКЦИОНАЛЬНОЙ ЭКВИВАЛЕНТНОСТИ КОНТАКТОВ МИКРОСХЕМ

3.1. Методы и критерии.

3.2. Использование функциональной эквивалентности контактов микросхем на этапе компоновки.

3.2.1. Определение расстояний на графовой модели схемы.

3.2.2. Алгоритм решения задачи назначения эквивалентных контактов.

3.2.3. Выбор метода решения задачи коммивояжера

3.3. Использование функциональной эквивалентности контактов микросхем на этапе размещения.

3.3.1. Оценка числа пересечений ребер двудольного графа

3.4. Использование функциональной эквивалентности контактов микросхем на этапе трассировки.

3.5. Выводы

IV. КОНТРОЛЬ КОНСТРУКТИВНО-ТЕХНОЛОГИЧЕСКИХ НАРУШЕНИЙ

В ТОПОЛОГИИ ПЕЧАТНОГО МОНТАЖА.

4.1. Особенности контроля конструктивно-технологических ограничений в гибкой топологической трассировке

4.2. Алгоритм проверки конструктивно-технологических нарушений в топологии печатного монтажа.

4.3. Выводы

V. ПРОГРАММНЫЙ КОМПЛЕКС ТОПОЛОГИЧЕСКОЙ ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ TopoR.

5.1. Основные сведения о системе TopoR

5.1.1. Требования системы к оборудованию.

5.1.2. Технические характеристики и ограничения

5.1.3. Режимы и функции

5.2. Программа проверки выполнения конструкторско-технологических ограничений (DRC).

5.3. Выводы

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы верификации топологии печатного монтажа»

Техническое проектирование является важнейшим этапом разработки радиоэлектронных средств (РЭС) различного назначения. На этом этапе определяется конструктивная реализация проектных идей и решений, формируются основные производственно-экономические и эксплуатационные характеристики будущих изделий. В результате технического проектирования описание (модель) разрабатываемого объекта достигает наиболее полного и детального уровня, необходимого для непосредственного материального воплощения проекта. Многообразие требований, ограничений и компонентов получают здесь конкретное единство.

Сложность радиоэлектронной аппаратуры неуклонно повышается. Не только увеличивается количество элементов на печатной плате или кристалле БИС, но и сами элементы становятся всё более сложными: увеличивается количество внешних контактов микросхем при одновременном уменьшении расстояний между контактами. В результате задача синтеза топологии соединений становится всё более и более трудной.

Вероятность того, что разработанная топология сразу же будет корректной, очень мала, так как невозможно полностью исключить «человеческий фактор» ни в одном методе проектирования, сколь бы автоматизированным он ни был. А человеку, как известно, свойственно ошибаться.

При проектировании топологии печатных плат (ПП) и интегральных схем (ИС) могут возникнуть ошибки, связанные с потерей соединений, с прокладкой лишних соединений и самое худшее - с перестановкой соединений. Тогда возникает ситуация, когда общее число связей и элементов соответствует заданному, но схема не работает. Поэтому важно еще до начала этапа изготовления фотошаблонов убедиться, что проектируемое устройство будет выполнять требуемые функции. Другими словами, удостовериться, что созданная топология соответствует реализуемой электрической схеме и заданным конструктивно-технологическим ограничениям (КТО).

Следовательно, необходимость введения в маршрут проектирования этапа верификации топологии вполне очевидна.

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

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

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

В соответствии с этим в работе ставились и решались следующие задачи:

- анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС;

- построение адекватных требованиям топологического синтеза моделей электрических схем проектируемых узлов, используемых на этапе верификации;

- разработка эффективного алгоритма определения изоморфности гиперграфов как теоретической основы задачи установления соответствия описания топологии печатного узла его принципиальной схеме;

- разработка методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа;

- разработка эффективных методов назначения функционально эквивалентных контактов микросхем на различных этапах проектирования топологии печатного монтажа;

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

- создание и адаптация к промышленным условиям эксплуатации быстродействующих программных средств автоматической верификации топологии узлов РЭС на печатных платах, микросборках и СБИС.

Научная новизна диссертационной работы заключается:

- в обосновании использования гиперграфовой модели электрической схемы устройства при решении задачи верификации печатных узлов РЭС;

- в разработке алгоритма определения изоморфности гиперграфов;

- в разработке методов получения оценки числа пересечений ребер линейной и циклической реализаций двудольного графа;

- в разработке методов переназначения функционально эквивалентных вентилей и контактов микросхем на различных этапах синтеза топологии печатного монтажа;

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

Практическая ценность работы состоит в создании прикладных программ, предназначенных для решения задачи верификации топологии печатного монтажа в автоматическом режиме. Применение разработанных программ обеспечивает улучшение качества и сокращение сроков проектирования СБИС и печатных узлов РЭС.

Результаты диссертационной работы в виде конкретных положений, выводов, методов, алгоритмов, машинных программ и расчетных данных внедрены и инженерную практику и используются на промышленных предприятиях в Москве, Санкт-Петербурге и Нижнем Новгороде, а также в учебном процессе СПбГУАП и СПбГЭТУ (ЛЭТИ). Акты, подтверждающие внедрение, приведены в приложении.

Основные положения и результаты диссертационной работы докладывались и были одобрены на следующих конференциях:

- III Международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 1999г;

- III научно-практической конференции "Современные информационные и электронные технологии", г. Одесса, 2002г.;

- VI международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2002г.;

- 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003 г.;

- 4-й международной НПК "Современные информационные и электронные технологии", Одесса, 2003 г.;

- VII международной научно-практической конференции "Системы и средства передачи и обработки информации", г. Одесса, 2003 г.;

- Международной научно-технической конференции HnH(CALS)-2003 "Информационные технологии в управлении жизненным циклом изделий", С.-Петербург, 2003г.;

- Всероссийской научно-практической конференции "Информационные технологии в российской промышленности", С.Петербург, 2004 г.;

- 5-й международной НПК "Современные информационные и электронные технологии", Одесса, 2004 г.;

- III международном симпозиуме "Аэрокосмические приборные технологии", С.-Петербург, 2004 г.;

- Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения", Сочи, 2004 г.;

- VIII международной научно-практической конференции "Системы и средства передачи и обработки информации", Одесса, 2004 г.;

- 6-й международной НПК "Современные информационные и электронные технологии", Одесса, 2005 г.

По теме диссертации опубликована 21 работа, из них 4 статьи и 17 тезисов к докладам на международных научно-технических конференциях.

Диссертация состоит из введения, пяти глав, заключения и приложения. Текстовый материал изложен на 121 странице.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Лузин, Михаил Сергеевич

5.3. Выводы

1. Разработан программный комплекс топологической трассировки печатного монтажа TopoR (от Topological Router).

2. Разработана программа контроля конструктивно-технологических ограничений с учетом особенностей топологической трассировки печатного монтажа.

3. Разработаны программные средства автоматизированного переназначения функционально эквивалентных контактов микросхем.

ЗАКЛЮЧЕНИЕ

Основные теоретические и практические результаты диссертационной работы заключаются в следующем.

1. Проведен анализ применяемых моделей и алгоритмов верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.

2. Показана неадекватность мультиграфовой модели принципиальной электрической схемы, традиционно используемой при решении задач верификации.

1. Обоснована необходимость использования модели принципиальной электрической схемы в виде гиперграфа.

2. Разработан алгоритм определения изоморфности гиперграфов как теоретической основы задачи установления соответствия описания топологии печатного узла и его принципиальной схемы.

3. Предложена новая функция для определения топологических расстояний на графе и алгоритм переназначения функционально эквивалентных контактов микросхем на этапе компоновки.

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

5. Разработаны эффективный алгоритм переназначения функционально эквивалентных контактов микросхем на этапе пробной трассировки соединений.

6. Разработаны структуры данных и алгоритмы контроля конструктивно-технологических нарушений в топологии печатного монтажа.

7. Разработаны быстродействующие программные средства автоматической верификации принципиальных схем и топологии узлов РЭС на печатных платах, микросборках и СБИС.

Список литературы диссертационного исследования кандидат технических наук Лузин, Михаил Сергеевич, 2005 год

1. Абрайтис Л.Б., Шнейкаускас Р.И., Жилявичус В.А. Автоматизация проектирования ЭВМ. - М.: Сов. радио, 1978, 272с.

2. Абрайтис Л.Б., Автоматизация проектирования топологии цифровых, интегральных микросхем. М.: Радио и связь, 1985, 197с.

3. Алгоритмические исследования в комбинаторике / Под ред. Фараджева И.А. -М.: Наука, 1978.

4. Арлазаров В.Л., Зуев И.В., Усков А.В., Фараджев И.А. Алгоритм приведения конечного неориентированного графа к каноническому виду. ЖВМ и МФ, 1974, 14, №3, с. 737-747.

5. Баранов С.И., Майоров С.А. Сахаров Э.П., Селютин В.А. Автоматизация проектирования цифровых устройств. Л.: Судостроение, 1979.-264с. . . .

6. Барышев А.И. Приложение гиперграфов к задаче трассировки. — В кн.: Автоматизация конструкторского проектирования радиоэлектронной и электронно-вычислительной аппаратуры. -Саратов: Изд-во Саратовского у-та, 1981, с.64-67.

7. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры. Л.: Энергия, 1979. -120с.

8. Батищев Д.И., Бершадский A.M., Щербань А.Б. Обобщенный критерий оценки качества разбиения графа на группы изоморфных подграфов. В кн.: Анализ и моделирование экономических процессов. - Горький: Изд-во Горьк. у-та, 1979, с. 3-9.

9. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. Изд. Саратовского университета, 1983,- 120с.

10. Бершадский A.M., Щербань А.Б., Игошина JI.B. Использование метода выделения в графе изоморфных подграфов для повышения эффективности алгоритмов размещения разногабаритных элементов. -Изв. ЛЭТИ, 1979, вып. 235, с. 105-109.

11. Берштейн Л.С. Селянкин В.В. Линейное размещение гиперграфов. -Изв. АН СССР, Техн. кибернетика, 1973. № 3, с. 128 -135.

12. Бибило П.Н., Лицкевич, В.Г. Покрытие булевой сети библиотечными элементами. Управляющие системы и машины, 1999, №6, с 16-24.

13. Вичес С.А. Асимптотический оптимально алгоритм перечисления пересечений ребер двудольного графа. Авт. и телемеханика, вып. 12. 1984, с.133-137.

14. Воротынцев В.Ю., Лузин М.С., Петросян Г.С. К оценке качества топологии печатного монтажа. // Труды III международного симпозиума "Аэрокосмические приборные технологии", — С.Петербург. 2004. - С. 175.

15. Воротынцев В.Ю., Лузин М.С., Петросян Г.С. Пути повышении плотности печатного монтажа. // Труды Международной научно-практической конференции "Фундаментальные и прикладные проблемы приборостроения". Сочи. - 2004. - С.

16. Горбатов В.А. Частотная матрица отношений и ее применения. Труды МЭИ. Вычислительная техника, 1964, т.53, с. 5-30.

17. Горбатов В.А. и др. Автоматизация проектирования сложных логических структур. М., Энергия, 1978.

18. Горбатов В.А. Теория частично упорядоченных систем. М., Сов. радио, 1976,-248 с.

19. Горбатов В.А. Семантическая теория проектирования автоматов. М., Энергия, 1979, 264 с.

20. Горбатов В.А., Павлов П.Г., Четвериков В.Н. Логическое управление информационными процессами. М., Энергоатомиздат, 1984, - 304 с.

21. Горбатов В.А. Основы дискретной математики. М., Высшая школа, 1986, - 311 с.

22. Деньдобренко Е.Н., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. -384с.

23. Дмитриев П.И., Лузин М.С., Лузин С.Ю., Колосов А.Н., Полубасов О.Б., Шубарев В.А. Система автоматизированного проектирования тонкопленочных микросборок "FreeStyleTF". // Технологии приборостроения. 2003. - №3. - С. 42-49.

24. Дмитриев П.И., Зудин С.В., Лузин М.С., Полубасов О.Б. Повышение эффективности силового размещения компонентов. // Технология и конструирование в электронной аппаратуре. 2003. — С.7-9.

25. Дмитриев П.И., Зудин С.В., Лузин М.С., Петросян Г.В., Полубасов О.Б. Учебная САПР тонкопленочных микросборок. // Труды 9-й международной конференции "Современные технологии обучения", С.-Петербург, 2003, т. 1., с. 196-197.

26. Дмитриев П.И., Зудин С.В., Лузин С.Ю., Лузин М.С., Петросян Г.С., Полубасов О.Б. Автоматизация синтеза топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. -С. 166.

27. Дюдин М.В., Лузин М.С., Петросян Г.С., Полубасов О.Б. Способ повышения плотности печатного монтажа. // Труды VIII международной научно-практической конференции "Системы и средства передачи и обработки информации". Одесса, 2004, с. 123.

28. Дюдин М.В., Лузин М.С., Петросян Г.С., Полубасов О.Б. Преимущества неортогональной топологии печатного монтажа. // Труды 5-й международной НПК "Современные информационные и электронные технологии". Одесса. - 2004. - С. 167.

29. Жижко В.А. Метод построения гиперграфа на плоскости. -Электронная техника, сер. 3. Микроэлектроника, 1979, вы. 6 (84), с. 78-85.

30. Зайченко В.А., Иванов А.В., Розенфельд М.З., Фараджев И.А. Алгоритм проверки каноничности частично-заполненной матрицы смежности графа. В кн.: Алгоритмические исследования в комбинаторике. М.: Наука, 1978 с. 19-24.

31. Зыков А.А. Гиперграфы. Успехи мат. наук, 1974, т. XXIX, вып. 6 (180), с. 89-154.

32. Зыков А. А. Основы теории графов. М.: Наука, 1987. - 384 с.

33. Кохов В.А. Диаграммы, числа стабильности и цикловые индексы групп автоморфизмов транзитивных графов. В сб. Исследования по прикладной теории графов /под ред. А.С. Алексеева. - Новосибирск, Наука, 1986,- 168с.

34. Кохов В.А., Ульяновский И.И. Исследование транзитивных графов, порожденных диаграммами Кели. Тр. Моск. энерг. ин-та, 1981, вып. 556, с. 29-35.

35. Кохов В.А., Ульяновский И.И. Алгоритм конструктивного перечисления графов с определенной группой автоморфизмов. Тр. Моск. энерг. ин-та, 1981, вып. 556, с. 36-42.

36. Кристофидес Н. Теория графов. М.: Мир, 1978. - 423 с.

37. Лузин С.Ю., Лячек Ю.Т., Полубасов О.Б. Автоматизация проектирования печатных плат. Система топологической трассировки TopoR. // СПб, СПбГЭТУ "ЛЭТИ". 2005. - 163 с.

38. Лузин М.С. Верификация топологии БИС и принципиальной схемы. Труды третьей международной научно-практической конференции "Современные информационные и электронные технологии". -Одесса, 2002, с. 172.

39. Лузин М.С. Изоморфизм гиперграфов и контроль топологии электронных схем. // Труды международной НТК "Системы и средства передачи и обработки информации". Одесса, 2202, с. 148.

40. Мелихов A.M., Берштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 304с.

41. Мелихов А.К., Берштейн Л.С., Селянкин В.В. Минимизация пересечений проводников в канале с помощью гиперграфов. АиВТ, 1977, № 4. С.77-82.

42. Петренко А.И., Тетельбаум А .Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Советское радио, 1979.-253с.

43. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977, 384с.

44. Соколов В.Е., Лузин М.С. К оценке числа пересечений ребер двудольного графа. // Труды четвертой международной научно-практической конференции "Современные информационные и электронные технологии". Одесса, 2003, с.211.

45. Соколов В.Е., Лузин М.С. Сравнительный анализ алгоритмов решения задачи коммивояжера. // Проблемы машиноведения и машиностроения. Межвузовский сборник. Вып. 29. С.-Петербург. -2003. С.131-143.

46. Соколов В.Е., Лузин М.С. Оценка числа пересечений ребер двудольного графа. // Проблемы машиноведения и машиностроения. Межвузовский сборник. Вып. 30. С.-Петербург. -2003. С.59-62.

47. Тетельбаум А.Я., Шрамченко Б.Л. Применение гиперграфов при исследовании планарности электронных схем. Изв. АН СССР, Техн. кибернетика, 1975. №5. С. 127-136.

48. Хопкрофт Дж.Е., Тарьян П.Е. Изоморфизм планарных графов. -Кибернетический сборник, вып. 12., 1975, с. 39-61.

49. A Library of TSP instances: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

50. Babai L., Kucera L. Canonical Labelling of Graphs in Linear Averageth

51. Time. Proc. 20 Symp. On Foundations of Сотр., Sci., Puerto Rico, 1979, pp.39-46.

52. Babai L. On the Complexity of Canonical Labelling of Strongly Regular Graphs. SIAM J. Сотр., 9,1980, pp.212-216.

53. Babai L. Automorphism group and category of cospectral graphs. Acta Math. Acad. Sci. Hung., 31, 1978, pp.295-306.

54. Babai L., Erdos P., Selkow S.M. Random Graph isomorphism. SIAM J. Сотр., 9 (1980), pp. 628-635.

55. Babai L., Grigoryev D., Y., Mount D.,M. Isomorphism of Graphs with Bounded Eigenvalue Multiplicity. - Proc. 14th Annual ACM Symp. On Theory of Computing, 1983, pp. 310-324.th

56. Babai L., Luks E.M. Canonical Labelling of Graphs. Proc. 15 Annual ACM Symp. On Theory of Computing, 1983, pp. 171-183.

57. Balahan A.T., Harary F. The Characteristic Polynomial Das Not Uniquely Determine the Topology of a Molecule. J. Of Chem. Doc., 11, 4 (1971), pp.258-259.

58. Bauersfeld G., Essman C., Lohle H. Ein Algorithmus zur Ferstellung der Isomorphie von Endlichen Graphen. Computing, 1, 2 (1979), 159-168.

59. Bermond J.c., Vergnas M. Regular Factors in Nearly Regular Graphs. -Dicrete Mathematics, 50 (1984), pp. 9-13.

60. Biggs N.L. Automorphism of imbedded Graphs. J. Comb. Theory, Bll (1971), pp.132-139.

61. Biggs N.L. Lloyd E.K., Wilson R.J. Graph Theory. Oxford, 1980, -239pp.

62. Bohm C., Santolini A. A quasi decision algorithm for the p- equivalence of two matrices. ICC Bull., 6, 1, 1964, 57-69.

63. Booth K.S. Isomorphism Testing for Graphs, Semigraphs and Finite Automatates are Polynomially. SIAM J. Сотр., 7, 9 (1978), pp. 213-279.

64. Borowiecki M. On Spectrum of Graphs. Publ. De Г Inst. Mathem. Nouvelle serie, t.39 (52), 1985, pp. 31-33.

65. Bose R.C., Shimamoto T. Classification and analysis of partially balanced incomplete block designes with two associated classes. J. Amer. Stat. Assoc., 47, 1952. Pp. 151-184.

66. Bose R.C. Strongly regular graphs partial geometries and partially balanced designs. J. Math., 1963, v.13, pp. 389-419.

67. Brown H., Hjelmeland L., Masinter L. Constructive Graph Labelling Using Double Cosets. Discrete Math., 7 (1974), pp.1-30.

68. Brualdi R.A., Solheid E.S. On the Specral Radins of Connected Graphs. -Publ. Inst. Math., Nouv. Serie, t.39 (53), 1986, pp.45-54.

69. Chandhary N.S., Sarda N.L., Phatak D.B. A note on the property of an adjoiner of the adjacency matrix of strongly regular graphs. Indian J. Pure and Appl. Math., 1986, 17, №7, pp. 871-874.

70. Christian R. An Isomorphism for Digital Imagies. J. Comb. Theory, 1985, A39,№2,pp. 132-159.

71. Corneil D.G., Goldberg M.K. On graph certificates. Proc. 13th Southeastern Conf. On Combinatorics, Graph Theory & Computing. Congr. Numer. 35 (1982), pp.181-189.

72. Corneil D.G., Goldberg M.K. A Non-factorial Algorithm for Canonical Numbering of a Graph. J. of Algorithms, 1984, Sept., v.5., No.3, pp.345362.

73. Corneil D.G., Gotlieb C.C. An efficient algorithm for graph isomorphism. -J. ACM, 17(1970), pp. 51-64.

74. Corneil D.G., Kirkpatrick D.G. A theoretical analysis of various heuristics for the graph isomorphism problem. SI AM J. on Comput., 9, 2 (1980), pp. 281-297.

75. Cosis O. A Formalism Relevant to a Classical Strategy for Graph Isomorphism Testing. Proc. 7th S.E. Conf. on Comb., Graph Theory and Computing. 1976, pp. 229-238.

76. Dewdney A.K. Tree Classes of Graph Invariants and their Powers. 9 S.E. Conf. on Comb., Graph Theory and Computing. 1978, pp. 243-264.

77. Dorigo M., L.M. Gambardella. Ant Colonies for the Traveling Salesman Problem. BioSystems, 43:73-81, 1997.

78. Droms С. Isomorphism graphs groups. Proc. of the Amer. Math. Soc., v.100., No.3, 1987, July, pp. 407-408.

79. Druppel L.E., Schmidt D.C., Simpson J.E. A Partitioning Isomorphism Algorithm for Directional Graphs using the F Matrix. Proc. 6th S.E. Conf. on Comb., Graph Theory and Computing, 1975.

80. Feigenbaum J., Schaffer A. Recognizing composite graphs is equivalent to testing graph isomorphism. SIAM J. Сотр., 1986, 15, №2, pp. 619627.

81. Gardner M.L. Hypergraphs and Whitney's theorem on edge-isomorphism of graphs. -Discr. Math., 1984, 51, №1, pp. 1-9.

82. Gati G. Further Annotated Bibliography on the Isomorphism Desease. J. Graph Theory, 3, 1979, pp. 95-109.

83. GATSS: Genetic Algorithm based solver of the Traveling Salesman problem, http://www.acc.umu.se/~top/travelinformation.html

84. GNU Scientific Library: http://sources.redhat.com/gsl/ref/gsl-ref toc.html

85. Harary F., Robinson R.W. Isomorphic Factorizations III: Bisectable Trees. Combinatorica, v.4, No. 2-3, 1984, pp. 169-179.

86. Hoffman C.M. Group theoretic algorithms and graph isomorphism. — Lecture Notes in Computer Science, v. 136, 1982, Berlin.

87. King C., Mowshowits A., Read R.C. Cospectral Graphs and Digraphs. -Bull. London Math., Soc., v.3, 1971, Nov., No.9, pp. 321-328.

88. Kureichic V., Bickart T. An Isomorphism Test for Homogenous Graphs. In Proc. Conf. On Information Science and Systems, USA, 1979.

89. Kureichic V., Tetelbaum A. Graph Isomorphism Algorithm for Regular VLSI Structure. Proc. 28th Annual Conf. on Information Science and Systems, Princeton, USA, March 1994, pp. 78-85.

90. Marcus Randall, David Abramson. An Empirical Study of State Encoding in Tabu Search. Technical Report 99-02, School of Information Technology, Bond University, 1999.

91. Martin, S.W. Otto, and E.W. Felten. Large-step Markov chains for the TSP incorporating local search heuristics. Oper. Res. Lett., 11:219—24, 1992.

92. Olivier C. Martin, Stewe W. Otto. Combining Simulated Annealing with Local Search Heuristics. Annals of Operations Research, vol. 63, pp. 57-75, 1996.

93. Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem. SIAM Journal on Discrete Mathematics, volume 10, number 2, pp. 171-179.

94. S. Reiter and G. Sherman. Discrete optimizing. SIAM Journal on Applied Mathematics 13, 864-889, 1965.

95. R.L. Karg and G.L. Thompson. A heuristic approach to solving travelling salesman problems. Management Science 10, 225-248, 1964.

96. Nesetril J., Poljak S. On the Complexity of the Subgraph Problem. -Comment. Math. Univ. Carol., 1985, 26, №2, pp. 415-419.

97. Patil H.P. Isomorphisms of duplicate graphs with some graph valued functions. J. Comb. Inf. And Sys. Sci., 1985, 10, №1-2, pp. 36-40.

98. Read R.C., Corneil D.G. The Graph Isomorphism Desease. J. Graph Theory, 1, 1977, pp. 339-363.

99. Rempel Joachim A heuristic 0(n5)-algorithm for nonisomorphism testing of graphs. "Graphs and Hipergreaphs and Appl. Proc. Conf. Graph Theory, Eyba, Oct, lth-5th" Leipzig, 1985, pp. 130-136.

100. Rigby M.J., Mallion R.B., Waller D.A. On the Quest for on Isomorphism Invariant which Characterizes Finite Chemical Graphs. -Chem. Phys. Lett., 1978, 59, №2, pp. 316-320.

101. Syslo Maciej M. The subgraph isomorphism problem for outerplanar graphs. Theor. Comput. Sci., 1981, 17, №1, pp. 91-97.

102. Tinhofer G. Graph isomorphism and theorems of Birkhoff type. -Computing, 1986, 36, №4, pp.285-300.

103. Tinhofer G. Zur Bestimmung der Automorphismen eines Endlichen Graphen. Computing, 15, №2, 1975, 147-156.

104. TSPBIB Home Page: http://www.ing.unlp.edu.ar/cetad/mos/ TSPBIB home.html

105. Turner J. Generalized Matrix Functions and the Graph Isomorphism Problem. SIAM J. Appl. Math., 16, №3, 1968, pp. 520-526.

106. Watanabe M. On the Characteristic Polynomial of a Multigraph. -Math. Rep. Toyama Univ., 1979, 2, pp. 87-94.

107. Weisfeiler B. On Construction and Identification of Graphs. Lecture Notes in Math., 1976.

108. Zemlyachenko V.N., Babai L. Moderately Exponential Bound for Graph Isomorphism. Proc. Conf. on Fundamentals of Computation Theory, 1982.