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

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

Topological Stack-Queue Mixed Layouts of Graphs 그래프의 토폴로지 스택-큐 혼합 레이아웃

Miki MIYAUCHI

  • 조회수

    0

  • 이것을 인용

요약 :

그래프 세분화의 스택-큐 혼합 레이아웃의 한 가지 목표는 스택과 큐의 수가 주어졌을 때 가장자리당 세분화 정점 수가 최소인 레이아웃을 얻는 것입니다. Dujmović와 Wood는 모든 정수에 대해 다음을 보여주었습니다. s, q>0, 모든 그래프 G ~을 가지고있다 s-스택 q-4⌈로그를 사용한 대기열 세분화 레이아웃(s+q)q sn(G)⌉ (각각 2+4⌈log(s+q)q qn(G)⌉) 모서리당 정점 분할, 여기서 sn(G) (관련 qn(G))는 다음의 스택 번호(각각 대기열 번호)입니다. G. 이 논문은 모든 정수에 대해 다음을 보여줌으로써 이러한 결과를 개선합니다. s, q>0, 모든 그래프 G ~을 가지고있다 s-스택 q-최대 2⌈로그를 포함하는 대기열 세분화 레이아웃s+q-1sn(G)⌉ (각각 최대 2⌈logs+q-1qn(G)⌉ +4) 모서리당 분할 정점. 즉, 이 논문은 더 큰 스택 번호 sn(G) 또는 대기열 번호 qn(G) 주어진 정수보다 s and q. 또한, 주어진 정수가 클수록 s 즉, 이 논문이 이전 결과를 더 많이 향상시킵니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E103-A No.2 pp.510-522
발행일
2020/02/01
공개일
온라인 ISSN
1745-1337
DOI
10.1587/transfun.2019EAP1097
원고의 종류
PAPER
범주
그래프와 네트워크

작성자

Miki MIYAUCHI
  NTT Corporation

키워드