Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science
Identifieur interne : 000556 ( Main/Curation ); précédent : 000555; suivant : 000557Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science
Auteurs : Akio Fujiyoshi [Japon] ; Masakazu Suzuki (mathématicien) [Japon]Source :
- IEICE transactions on information and systems [ 0916-8532 ] ; 2011.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
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.
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000144
- to stream PascalFrancis, to step Curation: Pour aller vers cette notice dans l'étape Curation :000629
- to stream PascalFrancis, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000110
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :000562
Links to Exploration step
Pascal:11-0220366Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science</title>
<author><name sortKey="Fujiyoshi, Akio" sort="Fujiyoshi, Akio" uniqKey="Fujiyoshi A" first="Akio" last="Fujiyoshi">Akio Fujiyoshi</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Computer and Information Sciences, Ibaraki University</s1>
<s2>Hitachi-shi, 316-8511</s2>
<s3>JPN</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Japon</country>
<wicri:noRegion>Hitachi-shi, 316-8511</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Suzuki, Masakazu" sort="Suzuki, Masakazu" uniqKey="Suzuki M" first="Masakazu" last="Suzuki">Masakazu Suzuki (mathématicien)</name>
<affiliation wicri:level="4"><inist:fA14 i1="02"><s1>Graduate School of Mathematics, Kyushu University</s1>
<s2>Fukuoka-shi, 819-0395</s2>
<s3>JPN</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Japon</country>
<placeName><settlement type="city">Fukuoka</settlement>
<region type="province">Kyūshū</region>
<region type="prefecture">Préfecture de Fukuoka</region>
</placeName>
<orgName type="university">Université de Kyūshū</orgName>
<placeName><settlement type="city">Fukuoka</settlement>
<region type="province">Kyūshū</region>
<region type="prefecture">Préfecture de Fukuoka</region>
</placeName>
<orgName type="university" n="3">Université de Kyūshū</orgName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">11-0220366</idno>
<date when="2011">2011</date>
<idno type="stanalyst">PASCAL 11-0220366 INIST</idno>
<idno type="RBID">Pascal:11-0220366</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000144</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000629</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000110</idno>
<idno type="wicri:doubleKey">0916-8532:2011:Fujiyoshi A:minimum:spanning:tree</idno>
<idno type="wicri:Area/Main/Merge">000562</idno>
<idno type="wicri:Area/Main/Curation">000556</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science</title>
<author><name sortKey="Fujiyoshi, Akio" sort="Fujiyoshi, Akio" uniqKey="Fujiyoshi A" first="Akio" last="Fujiyoshi">Akio Fujiyoshi</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Computer and Information Sciences, Ibaraki University</s1>
<s2>Hitachi-shi, 316-8511</s2>
<s3>JPN</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Japon</country>
<wicri:noRegion>Hitachi-shi, 316-8511</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Suzuki, Masakazu" sort="Suzuki, Masakazu" uniqKey="Suzuki M" first="Masakazu" last="Suzuki">Masakazu Suzuki (mathématicien)</name>
<affiliation wicri:level="4"><inist:fA14 i1="02"><s1>Graduate School of Mathematics, Kyushu University</s1>
<s2>Fukuoka-shi, 819-0395</s2>
<s3>JPN</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>Japon</country>
<placeName><settlement type="city">Fukuoka</settlement>
<region type="province">Kyūshū</region>
<region type="prefecture">Préfecture de Fukuoka</region>
</placeName>
<orgName type="university">Université de Kyūshū</orgName>
<placeName><settlement type="city">Fukuoka</settlement>
<region type="province">Kyūshū</region>
<region type="prefecture">Préfecture de Fukuoka</region>
</placeName>
<orgName type="university" n="3">Université de Kyūshū</orgName>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">IEICE transactions on information and systems</title>
<title level="j" type="abbreviated">IEICE trans. inf. syst.</title>
<idno type="ISSN">0916-8532</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">IEICE transactions on information and systems</title>
<title level="j" type="abbreviated">IEICE trans. inf. syst.</title>
<idno type="ISSN">0916-8532</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Labelled graph</term>
<term>Minimum spanning tree MST</term>
<term>NP hard problem</term>
<term>Optical character recognition</term>
<term>Pattern recognition</term>
<term>Series parallel connection</term>
<term>Time series</term>
<term>Tree(graph)</term>
<term>Vertex(graph)</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Arbre recouvrant minimal</term>
<term>Sommet graphe</term>
<term>Graphe marqué</term>
<term>Reconnaissance optique caractère</term>
<term>Problème NP difficile</term>
<term>Arbre graphe</term>
<term>Série temporelle</term>
<term>Algorithme</term>
<term>Montage série parallèle</term>
<term>Reconnaissance forme</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000556 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 000556 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= OcrV1 |flux= Main |étape= Curation |type= RBID |clé= Pascal:11-0220366 |texte= Minimum Spanning Tree Problem with Label Selection : Foundations of Computer Science - Mathematical Foundations and Apllications of Algorithms and Computer Science }}
This area was generated with Dilib version V0.6.32. |