Максимальный подграф общего ребра

Учитывая два графика $G$ и $G'$ , проблема максимального общего реберного подграфа - это проблема поиска графа $H$ с максимально возможным количеством ребер, изоморфен как подграфу который $G$ и подграф $G'$ .

Задача о максимальном общем реберном подграфе на общих графах является NP-полной , поскольку она является обобщением изоморфизма подграфов : граф $H$ изоморфен подграфу другого графа $G$ тогда и только тогда, когда максимальный общий реберный подграф $G$ и $H$ имеет то же количество ребер, что и $H$ . Если два входа $G$ и $G'$ Для решения задачи о максимальном общем реберном подграфе требуется одинаковое количество вершин, проблема является APX-сложной . ^[1]

См. также

Ссылки

^ Баиенсе, Л.; Маник, Г.; Пива, Б.; де Соуза, CC (2012), «Проблема о максимальном общем реберном подграфе: многогранное исследование», Discrete Applied Mathematics , 160 (18): 2523–2541, doi : 10.1016/j.dam.2012.01.026 .

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

Эта теории графов статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Баиенсе, Л.; Маник, Г.; Пива, Б.; де Соуза, CC (2012), «Проблема о максимальном общем реберном подграфе: многогранное исследование», Discrete Applied Mathematics , 160 (18): 2523–2541, doi : 10.1016/j.dam.2012.01.026 .

[1]