2021-03-09T08:13:02Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000904052020-04-01T00:33:29Z01164:02592:07086:07087
Algorithm for the Minimum Caterpillar Problem with TerminalsAlgorithm for the Minimum Caterpillar Problem with Terminalsenghttp://id.nii.ac.jp/1001/00090388/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=90405&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of JapanGraduate 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.Taku, OkadaAkira, SuzukiTakehiro, ItoXiao, ZhouSuppose 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|).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|).AN1009593X研究報告アルゴリズム（AL）2013-AL-1431172013-02-222013-02-15