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

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

Minimum Spanning Tree Problem with Label Selection 레이블 선택과 관련된 최소 스패닝 트리 문제

Akio FUJIYOSHI, Masakazu SUZUKI

  • 조회수

    0

  • 이것을 인용

요약 :

본 논문에서는 레이블 선택에 따른 최소 스패닝 트리 문제, 즉 정점 레이블 선택에 따라 각 간선의 가중치가 달라질 수 있는 정점 레이블 그래프의 최소 스패닝 트리를 찾는 문제를 연구합니다. 끝납니다. 이 문제는 수학적 OCR에 적용할 때 특히 중요합니다. 문제는 NP-hard인 것으로 나타났습니다. 그러나 수학적 OCR에 적용하려면 트리 너비가 작은 그래프만 처리하면 충분합니다. 본 논문에서는 직렬-병렬 그래프를 위한 선형 시간 알고리즘을 제시합니다. 라벨 선택에 관한 최소 스패닝 트리 문제는 일반화된 최소 스패닝 트리 문제와 밀접한 관련이 있으므로 이들의 관계를 논의한다.

발행
IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.233-239
발행일
2011/02/01
공개일
온라인 ISSN
1745-1361
DOI
10.1587/transinf.E94.D.233
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)
범주

작성자

키워드