Queue Layout of Bipartite Graph Subdivisions(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
For an integer d>0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmovic and D. R. Wood showed that for every integer d≥2, every graph G has a d-queue layout of a subdivision of G with 2「log_dqn(G)」+1 division vertices per edge, where qn(G) is the queue number of G. This paper improves the result for the case of a bipartite graph, and shows that for every integer d≥2, every bipartite graph G_<m,n> has a d-queue layout of a subdivision of G_<m,n> with 「log_dn」-1 division vertices per edge, where m and n are numbers of vertices of the partite sets of G_<m,n> (m≥n).
一般社団法人電子情報通信学会の論文
2007-05-01