Algorithm for the Minimum Caterpillar Problem with Terminals

• Item type: SIG Technical Reports(1)
• 公開日: 2013-02-22
• タイトル: Algorithm for the Minimum Caterpillar Problem with Terminals
• タイトル / 言語: en
• タイトル: Algorithm for the Minimum Caterpillar Problem with Terminals
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Graduate School of Information Sciences, Tohoku University.
• 著者所属: Graduate School of Information Sciences, Tohoku University.
• 著者所属: Graduate School of Information Sciences, Tohoku University.
• 著者所属: Graduate School of Information Sciences, Tohoku University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Sciences, Tohoku University.
• 著者名: Taku, Okada; Akira, Suzuki; Takehiro, Ito; Xiao, Zhou
• 著者名(英): Taku, Okada; Akira, Suzuki; Takehiro, Ito; Xiao, Zhou
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Suppose that each arc in a digraph D = (V, A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard even for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Suppose that each arc in a digraph D = (V, A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard even for three terminals. We then give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2013-AL-143, 号 1, p. 1-7, 発行日 2013-02-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会