Minimum Spanning Tree Problem with Label Selection
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we study the minimum spanning tree problem with label selection, that is, the problem of finding a minimum spanning tree of a vertex-labeled graph where the weight of each edge may vary depending on the selection of labels of vertices at both ends. The problem is especially important as the application to mathematical OCR. It is shown that the problem is NP-hard. However, for the application to mathematical OCR, it is sufficient to deal with only graphs with small tree-width. In this paper, a linear-time algorithm for series-parallel graphs is presented. Since the minimum spanning tree problem with label selection is closely related to the generalized minimum spanning tree problem, their relation is discussed.
著者
-
Fujiyoshi Akio
Department Of Computer And Information Sciences Ibaraki University
-
SUZUKI Masakazu
Graduate School of Mathematics, Kyushu University
-
Suzuki Masakazu
Graduate School Of Agricultural And Life Science The University Of Tokyo
関連論文
- Minimum Spanning Tree Problem with Label Selection
- The Relation between Unary Parameter Macro Tree Transducers and Spine Grammars
- Vertical Profiles of Environmental Factors within Tropical Rainforest, Lambir Hills National Park, Sarawak, Malaysia
- Multi-Phase Tree Transformations
- Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars(Automata and Formal Language Theory)
- Relationship between Nighttime Wind Speeds and Thermal Conditions above a Sloping Forest
- Application of the CKY Algorithm to Recognition of Tree Structures for Linear, Monadic Context-Free Tree Grammars(Formal Languages,Foundations of Computer Science)
- Seasonality of vertically partitioned soil CO_2 production in temperate and tropical forest
- A Model of Equity Prices with Heterogeneous Beliefs
- Altitudinal increase in rainfall in the Mae Chaem watershed, Thailand
- Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata
- Characteristics of Soil Temperature and Heat Flux within a Tropical Rainforest, Lambir Hills National Park, Sarawak, Malaysia
- Water Resources Observation and Large-scale Model Estimation in Forested Areas in Mekong River Basin
- Relationship between catchment scale and the spatial variability of stream discharge and chemistry in a catchment with multiple geologies
- Circumferential sap flow variation in the trunks of Japanese cedar and cypress trees growing on a steep slope