Search this article in Google Scholar


分類 論文誌
著者名 (author) Satoshi Fujita
英文著者名 (author)
キー (key)
表題 (title) Polynomial Time Algorithm for Constructing Vertex-Disjoint Paths in Transposition Graphs
表題 (英文)
定期刊行物名 (journal) Networks, An International Journal
定期刊行物名 (英文)
巻数 (volume) 56
号数 (number) 2
ページ範囲 (pages) 149-157
刊行月 (month) September
出版年 (year) 2010
付加情報 (note) DOI: 10.1002/net.20356
注釈 (annote) http://onlinelibrary.wiley.com/doi/10.1002/net.20356/abstract
内容梗概 (abstract) A transposition graph is a Cayley graph in which each vertex corresponds to a permutation and an edge is placed between permutations iff they differ by exactly one transposition. In this article, we propose an efficient algorithm to find a collection of vertex-disjoint paths connecting a given source vertex s and a given set of destination vertices D. The running time of the algorithm is polynomial in the number of destination vertices, and the resultant path connecting s and each destination is longer than the distance to the destination by at most 16.
論文電子ファイル Not available.


[0-43]  Satoshi Fujita, ``Polynomial Time Algorithm for Constructing Vertex-Disjoint Paths in Transposition Graphs,'' Networks, An International Journal, vol. 56, no. 2, pp. 149-157, September 2010.

@article{0_43,
    author = {Satoshi Fujita},
    author_e = {},
    title = {Polynomial Time Algorithm  for Constructing Vertex-Disjoint Paths
    in Transposition Graphs},
    title_e = {},
    journal = {Networks, An International Journal},
    journal_e = {},
    volume = {56},
    number = {2},
    pages = {149-157},
    month = {September},
    year = {2010},
    note = {DOI: 10.1002/net.20356},
    annote = {http://onlinelibrary.wiley.com/doi/10.1002/net.20356/abstract}
}

This site is maintained by Distributed System Laboratory.

PMAN 2.5.5 - Paper MANagement system / (C) 2002-2008, Osamu Mizuno / All rights reserved.