해밀턴 완성

Hamiltonian completion

해밀턴 완성 문제는 그래프가 해밀턴이 되도록 그래프에 추가할 최소 에지 수를 찾는 것입니다.

이 문제는 일반적으로 NP-hard이다(그 해답은 주어진 그래프가 해밀턴 주기를 가지는지 여부를 결정하는 NP-완전 문제에 대한 답을 제공하기 때문이다).해밀턴 그래프를 생성하기 위해 주어진 그래프에 K 모서리를 추가할 수 있는지 여부를 결정하는 관련 결정 문제는 NP-완전입니다.

더욱이, 해밀턴 완성은 APX 복잡도 클래스에 속합니다. 즉, 이 [1]문제에 대한 효율적인 상수 비율 근사 알고리즘이 존재할 가능성은 낮습니다.

이 문제는 나무 또는[4][5] 선인장의 [6]선 그래프뿐만 아니라 직렬-병렬[2] 그래프와 그 [3]일반화를 포함한 특정 클래스의 그래프에 대해 다항식 시간 내에 해결할 수 있다.

가마닉 등선형 시간 알고리즘을 사용하여 나무의 문제를 해결하여 희박한 랜덤 그래프에 추가해야 하는 점근적 에지 수를 연구하여 해밀턴 [7]그래프를 만듭니다.

레퍼런스

  1. ^ Q. S. Wu, C. L. Lu, R. C. T. Lee, 트리의 가중 해밀턴 경로 완성 문제를 위한 근사 알고리즘, 컴퓨터 과학 강의 노트, Vol. 1969 (2000) 페이지: 156 - 167
  2. ^ 를 클릭합니다Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328.
  3. ^ N. M. 코네옌코, 그래프 클래스에 대한 조합 알고리즘, 이산 응용 수학, v.54 n.2-3, 페이지 215-217, 1994
  4. ^ Arundhati Raychaudhuri, 트리의 총 간격 수 및 선 그래프의 해밀턴 완료 수, Volume 56, Issue 6 (1995년 12월) 299 - 306
  5. ^ A. Agnetis, P. Detti, C.멜로니, DPacciarelli, 트리의 선 그래프의 해밀턴 완료 번호에 대한 선형 알고리즘, Volume 79, Issue 1 (2001년 5월), 17 - 24
  6. ^ Paolo Detti, Carlo Meloni, 선인장의 직선 그래프의 해밀턴 완료 번호에 대한 선형 알고리즘, 이산 응용 수학, 제136권, 제2-3호(2004년 2월) 197 - 215호
  7. ^ David Gamarnik, Maxim Sviridenko, 희박한 랜덤 그래프의 해밀턴 완성, 이산 응용 수학 152 (2005) 139 – 158