Arată înregistrarea sumară a articolului
Counting Minimum Cost Bounded Degree Subtrees in Graphs with Small 2-Vertex-Connected Components
dc.contributor.author | Andreica, Mugurel Ionuţ | |
dc.date.accessioned | 2016-01-06T07:34:39Z | |
dc.date.available | 2016-01-06T07:34:39Z | |
dc.date.issued | 2013 | |
dc.identifier.issn | 1221-454X | |
dc.identifier.uri | http://10.11.10.50/xmlui/handle/123456789/3778 | |
dc.description | The Annals of "Dunarea de Jos" University of Galati | en_US |
dc.description.abstract | In this paper we present new algorithms for counting minimum cost bounded degree subtrees in connected graphs in which the 2-vertex-connected (biconnected) components have small sizes. The 2-vertex-connected components and the cut vertices can be organized into a block-cut vertex tree which is also a tree decomposition with small width of the graph. We present a dynamic programming algorithm which is very efficient on this particular tree decomposition and we also discuss methods of solving the problem given an arbitrary tree decomposition with small width. Among some of the most important results is an algorithm which can efficiently compute the number of subtrees of a (small) graph corresponding to each possible degree sequence. | en_US |
dc.language.iso | en | en_US |
dc.publisher | "Dunarea de Jos" University of Galati | en_US |
dc.subject | tree decomposition | en_US |
dc.subject | 2-vertex-connected components | en_US |
dc.subject | block-cut vertex tree | en_US |
dc.subject | bounded-degree subtree | en_US |
dc.title | Counting Minimum Cost Bounded Degree Subtrees in Graphs with Small 2-Vertex-Connected Components | en_US |
dc.type | Article | en_US |