검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

The Complexity of Embedding of Acyclic Graphs into Grids with Minimum Congestion 혼잡을 최소화하면서 비순환 그래프를 그리드에 삽입하는 복잡성

Akira MATSUBAYASHI, Masaya YOKOTA

  • 조회수

    0

  • 이것을 인용

요약 :

평면 그래프가 주어졌을 때 결정하는 문제는 다음과 같이 알려져 있습니다. G 그리고 정수 mn, 혼잡-1 임베딩이 존재하는지 여부 G 2차원으로 mn-grid는 NP-완전입니다. 이 논문에서는 다음과 같은 경우 문제가 여전히 NP-완전임을 보여줍니다. G 비순환 그래프로 제한됩니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.11 pp.2390-2394
발행일
2000/11/25
공개일
온라인 ISSN
DOI
원고의 종류
LETTER
범주
그래프와 네트워크

작성자

키워드