Vychislitelnaja slozhnost zadachi raspoznavanija izomorfnykh grafov

Вычислительная сложность задачи распознавания изоморфных графов

• Tekijä(t): Dudov M. Kh.
• Kieli: Venäjä
• Mitat: 205/130 mm
• Kustantaja: Radiosoft
• Ilmestymisvuosi: 2013
• Sidosasu: Pehmeä kansi
• Sivumäärä: 60
• ISBN: 978-5-93274-074-3

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