Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
Identifieur interne : 001693 ( Istex/Corpus ); précédent : 001692; suivant : 001694Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
Auteurs : Guoqiang Bai ; Henning FernauSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2008.
Abstract
Abstract: constraint bipartite vertex cover is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations.
Url:
DOI: 10.1007/978-3-540-69311-6_10
Links to Exploration step
ISTEX:117BD01AE315E38544A1808002A02C13AA8EF8CALe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title><author><name sortKey="Bai, Guoqiang" sort="Bai, Guoqiang" uniqKey="Bai G" first="Guoqiang" last="Bai">Guoqiang Bai</name><affiliation><mods:affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: baiguoqiang@hotmail.com</mods:affiliation></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><mods:affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fernau@uni-trier.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:117BD01AE315E38544A1808002A02C13AA8EF8CA</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/978-3-540-69311-6_10</idno><idno type="url">https://api.istex.fr/document/117BD01AE315E38544A1808002A02C13AA8EF8CA/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001693</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001693</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title><author><name sortKey="Bai, Guoqiang" sort="Bai, Guoqiang" uniqKey="Bai G" first="Guoqiang" last="Bai">Guoqiang Bai</name><affiliation><mods:affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: baiguoqiang@hotmail.com</mods:affiliation></affiliation></author><author><name sortKey="Fernau, Henning" sort="Fernau, Henning" uniqKey="Fernau H" first="Henning" last="Fernau">Henning Fernau</name><affiliation><mods:affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: fernau@uni-trier.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2008</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">117BD01AE315E38544A1808002A02C13AA8EF8CA</idno><idno type="DOI">10.1007/978-3-540-69311-6_10</idno><idno type="ChapterID">10</idno><idno type="ChapterID">Chap10</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: constraint bipartite vertex cover is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Guoqiang Bai</name><affiliations><json:string>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</json:string><json:string>E-mail: baiguoqiang@hotmail.com</json:string></affiliations></json:item><json:item><name>Henning Fernau</name><affiliations><json:string>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</json:string><json:string>E-mail: fernau@uni-trier.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: constraint bipartite vertex cover is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations.</abstract><qualityIndicators><score>7.172</score><pdfVersion>1.6</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>412</abstractCharCount><pdfWordCount>5268</pdfWordCount><pdfCharCount>26105</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>56</abstractWordCount></qualityIndicators><title>Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title><chapterId><json:string>10</json:string><json:string>Chap10</json:string></chapterId><refBibs><json:item><host><author><json:item><name>G Bai</name></json:item></author><title>Ein eingeschränktes Knotenüberdeckungsproblem in bipartiten Graphen</title><publicationDate>2007</publicationDate></host></json:item><json:item><author><json:item><name>D,M Blough</name></json:item></author><host><pages><last>451</last><first>444</first></pages><author></author><title>Fault Tolerant Computing</title><publicationDate>1991</publicationDate></host><title>On the reconfiguration of memory arrays containing clustered faults</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>D,M Blough</name></json:item><json:item><name>A Pelc</name></json:item></author><host><volume>42</volume><pages><last>528</last><first>518</first></pages><issue>5</issue><author></author><title>IEEE Transactions on Computers</title><publicationDate>1993</publicationDate></host><title>A clustered failure model for the memory array reconfiguration problem</title><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>J Chen</name></json:item><json:item><name>I,A Kanj</name></json:item></author><host><volume>67</volume><pages><last>847</last><first>833</first></pages><author></author><title>Journal of Computer and System Sciences</title><publicationDate>2003</publicationDate></host><title>Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithmics</title><publicationDate>2003</publicationDate></json:item><json:item><host><author><json:item><name>R,G Downey</name></json:item><json:item><name>M,R Fellows</name></json:item></author><publicationDate>1999</publicationDate></host></json:item><json:item><author><json:item><name>R,C Evans</name></json:item></author><host><pages><last>55</last><first>49</first></pages><author></author><title>Proceedings of the IEEE Int'l Test Conf</title><publicationDate>1981</publicationDate></host><title>Testing repairable RAMs and mostly good memories</title><publicationDate>1981</publicationDate></json:item><json:item><author><json:item><name>H Fernau</name></json:item></author><host><pages><last>573</last><first>564</first></pages><author></author><title>CO- COON 2002</title><publicationDate>2002</publicationDate></host><title>On parameterized enumeration</title><publicationDate>2002</publicationDate></json:item><json:item><host><author><json:item><name>H Fernau</name></json:item></author><title>Parameterized Algorithmics: A Graph-Theoretic Approach, Habilitationsschrift</title><publicationDate>2005</publicationDate></host></json:item><json:item><author><json:item><name>H Fernau</name></json:item><json:item><name>R Niedermeier</name></json:item></author><host><volume>38</volume><pages><last>410</last><first>374</first></pages><issue>2</issue><author></author><title>Journal of Algorithms</title><publicationDate>2001</publicationDate></host><title>An efficient exact algorithm for constraint bipartite vertex cover</title><publicationDate>2001</publicationDate></json:item><json:item><author><json:item><name>R,W Haddad</name></json:item><json:item><name>A,T Dahbura</name></json:item><json:item><name>A,B Sharma</name></json:item></author><host><volume>40</volume><pages><last>166</last><first>154</first></pages><issue>2</issue><author></author><title>IEEE Transactions on Computers</title><publicationDate>1991</publicationDate></host><title>Increased throughput for the testing and repair of RAMs with redundancy</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>K Handa</name></json:item><json:item><name>K Haruki</name></json:item></author><host><pages><last>1130</last><first>1123</first></pages><issue>6</issue><author></author><title>IEICE Trans. Fundamentals E83-A</title><publicationDate>2000</publicationDate></host><title>A reconfiguration algorithm for memory arrays containing faulty spares</title><publicationDate>2000</publicationDate></json:item><json:item><author><json:item><name>I Koren</name></json:item><json:item><name>D,K Pradhan</name></json:item></author><host><volume>36</volume><pages><last>355</last><first>344</first></pages><issue>3</issue><author></author><title>IEEE Transactions on Computers</title><publicationDate>1987</publicationDate></host><title>Modeling the effect of redundancy on yield and performance of VLSI systems</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>S.-Y Kuo</name></json:item><json:item><name>W,K Fuchs</name></json:item></author><host><volume>4</volume><pages><last>31</last><first>24</first></pages><author></author><title>IEEE Design and Test</title><publicationDate>1987</publicationDate></host><title>Efficient spare allocation for reconfigurable arrays</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>H.-Y Lin</name></json:item><json:item><name>F.-M Yeh</name></json:item><json:item><name>S.-Y Kuo</name></json:item></author><host><volume>55</volume><pages><last>378</last><first>369</first></pages><issue>2</issue><author></author><title>IEEE Transactions on Reliability</title><publicationDate>2006</publicationDate></host><title>An efficient algorithm for spare allocation problems</title><publicationDate>2006</publicationDate></json:item><json:item><author><json:item><name>F Lombardi</name></json:item><json:item><name>W,K Huang</name></json:item></author><host><pages><last>347</last><first>342</first></pages><author></author><title>International Symposium on Fault-Tolerant Computing</title><publicationDate>1988</publicationDate></host><title>Approaches to the repair of VLSI/WSI PRAMs by row/column deletion</title><publicationDate>1988</publicationDate></json:item><json:item><author><json:item><name>F,J Meyer</name></json:item><json:item><name>D,K Pradhan</name></json:item></author><host><volume>38</volume><pages><last>546</last><first>538</first></pages><issue>4</issue><author></author><title>IEEE Transactions on Computers</title><publicationDate>1989</publicationDate></host><title>Modeling defect spatial distribution</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>W Shi</name></json:item><json:item><name>W,K Fuchs</name></json:item></author><host><volume>11</volume><pages><last>1160</last><first>1153</first></pages><issue>9</issue><author></author><title>IEEE Transactions on Computer-Aided Design</title><publicationDate>1992</publicationDate></host><title>Probabilistic analysis and algorithms for reconfiguration of memory arrays</title><publicationDate>1992</publicationDate></json:item><json:item><author><json:item><name>J Wang</name></json:item><json:item><name>X Xu</name></json:item><json:item><name>Y Liu</name></json:item></author><host><volume>4616</volume><pages><last>353</last><first>343</first></pages><author></author><title>LNCS</title><publicationDate>2007</publicationDate></host><title>An Exact Algorithm Based on Chain Implication for the Min-CVCB Problem</title><publicationDate>2007</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>David Hutchison</name></json:item><json:item><name>Takeo Kanade</name></json:item><json:item><name>Josef Kittler</name></json:item><json:item><name>Jon M. Kleinberg</name></json:item><json:item><name>Friedemann Mattern</name></json:item><json:item><name>John C. Mitchell</name></json:item><json:item><name>Moni Naor</name></json:item><json:item><name>Oscar Nierstrasz</name></json:item><json:item><name>C. Pandu Rangan</name></json:item><json:item><name>Bernhard Steffen</name></json:item><json:item><name>Madhu Sudan</name></json:item><json:item><name>Demetri Terzopoulos</name></json:item><json:item><name>Doug Tygar</name></json:item><json:item><name>Moshe Y. Vardi</name></json:item><json:item><name>Gerhard Weikum</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>2008</copyrightDate></serie><host><editor><json:item><name>Franco P. Preparata</name></json:item><json:item><name>Xiaodong Wu</name></json:item><json:item><name>Jianping Yin</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item><json:item><value>Numeric Computing</value></json:item><json:item><value>Computer Graphics</value></json:item><json:item><value>Computational Biology/Bioinformatics</value></json:item><json:item><value>Algorithms</value></json:item></subject><isbn><json:string>978-3-540-69310-9</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Frontiers in Algorithmics</title><bookId><json:string>978-3-540-69311-6</json:string></bookId><volume>5059</volume><pages><last>78</last><first>67</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-69311-6</json:string></eisbn><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-69311-6</json:string></doi></host><publicationDate>2008</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/978-3-540-69311-6_10</json:string></doi><id>117BD01AE315E38544A1808002A02C13AA8EF8CA</id><score>0.6743621</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/117BD01AE315E38544A1808002A02C13AA8EF8CA/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/117BD01AE315E38544A1808002A02C13AA8EF8CA/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/117BD01AE315E38544A1808002A02C13AA8EF8CA/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2008</p></availability><date>2008</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title><author xml:id="author-1"><persName><forename type="first">Guoqiang</forename><surname>Bai</surname></persName><email>baiguoqiang@hotmail.com</email><affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Henning</forename><surname>Fernau</surname></persName><email>fernau@uni-trier.de</email><affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</affiliation></author></analytic><monogr><title level="m">Frontiers in Algorithmics</title><title level="m" type="sub">Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings</title><idno type="pISBN">978-3-540-69310-9</idno><idno type="eISBN">978-3-540-69311-6</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/978-3-540-69311-6</idno><idno type="book-ID">978-3-540-69311-6</idno><idno type="book-title-ID">162354</idno><idno type="book-sequence-number">5059</idno><idno type="book-volume-number">5059</idno><idno type="book-chapter-count">35</idno><editor><persName><forename type="first">Franco</forename><forename type="first">P.</forename><surname>Preparata</surname></persName></editor><editor><persName><forename type="first">Xiaodong</forename><surname>Wu</surname></persName></editor><editor><persName><forename type="first">Jianping</forename><surname>Yin</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2008"></date><biblScope unit="volume">5059</biblScope><biblScope unit="page" from="67">67</biblScope><biblScope unit="page" to="78">78</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName></editor><editor><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName></editor><biblScope><date>2008</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">117BD01AE315E38544A1808002A02C13AA8EF8CA</idno><idno type="DOI">10.1007/978-3-540-69311-6_10</idno><idno type="ChapterID">10</idno><idno type="ChapterID">Chap10</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2008</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: constraint bipartite vertex cover is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>I17028</label><label>I1701X</label><label>I22013</label><label>I23050</label><label>M14018</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Discrete Mathematics in Computer Science</term></item><item><term>Numeric Computing</term></item><item><term>Computer Graphics</term></item><item><term>Computational Biology/Bioinformatics</term></item><item><term>Algorithms</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2008">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/117BD01AE315E38544A1808002A02C13AA8EF8CA/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" OutputMedium="All" TocLevels="0"><BookID>978-3-540-69311-6</BookID><BookTitle>Frontiers in Algorithmics</BookTitle><BookSubTitle>Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings</BookSubTitle><BookVolumeNumber>5059</BookVolumeNumber><BookSequenceNumber>5059</BookSequenceNumber><BookDOI>10.1007/978-3-540-69311-6</BookDOI><BookTitleID>162354</BookTitleID><BookPrintISBN>978-3-540-69310-9</BookPrintISBN><BookElectronicISBN>978-3-540-69311-6</BookElectronicISBN><BookChapterCount>35</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="I17028" Priority="2" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><BookSubject Code="I1701X" Priority="3" Type="Secondary">Numeric Computing</BookSubject><BookSubject Code="I22013" Priority="4" Type="Secondary">Computer Graphics</BookSubject><BookSubject Code="I23050" Priority="5" Type="Secondary">Computational Biology/Bioinformatics</BookSubject><BookSubject Code="M14018" Priority="6" Type="Secondary">Algorithms</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Franco</GivenName><GivenName>P.</GivenName><FamilyName>Preparata</FamilyName></EditorName><Contact><Email>franco@cs.brown.edu</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Xiaodong</GivenName><FamilyName>Wu</FamilyName></EditorName><Contact><Email>xiaodong-wu@uiowa.edu</Email></Contact></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Jianping</GivenName><FamilyName>Yin</FamilyName></EditorName><Contact><Email>jpyin@nudt.edu.cn</Email></Contact></Editor></EditorGroup></BookHeader><Chapter ID="Chap10" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>10</ChapterID><ChapterDOI>10.1007/978-3-540-69311-6_10</ChapterDOI><ChapterSequenceNumber>10</ChapterSequenceNumber><ChapterTitle Language="En"><Emphasis Type="SmallCaps">Constraint Bipartite Vertex Cover</Emphasis> Simpler Exact Algorithms and Implementations</ChapterTitle><ChapterFirstPage>67</ChapterFirstPage><ChapterLastPage>78</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>978-3-540-69311-6</BookID><BookTitle>Frontiers in Algorithmics</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Guoqiang</GivenName><FamilyName>Bai</FamilyName></AuthorName><Contact><Email>baiguoqiang@hotmail.com</Email></Contact></Author><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Henning</GivenName><FamilyName>Fernau</FamilyName></AuthorName><Contact><Email>fernau@uni-trier.de</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>Univ. Trier, FB IV—Abteilung Informatik</OrgName><OrgAddress><Postcode>54286</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para><Emphasis Type="SmallCaps">constraint bipartite vertex cover</Emphasis> is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations</title></titleInfo><name type="personal"><namePart type="given">Guoqiang</namePart><namePart type="family">Bai</namePart><affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</affiliation><affiliation>E-mail: baiguoqiang@hotmail.com</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Henning</namePart><namePart type="family">Fernau</namePart><affiliation>Univ. Trier, FB IV—Abteilung Informatik, 54286, Trier, Germany</affiliation><affiliation>E-mail: fernau@uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2008</dateIssued><copyrightDate encoding="w3cdtf">2008</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: constraint bipartite vertex cover is a graph-theoretical formalization of the spare allocation problem for reconfigurable arrays. We report on an implementation of a parameterized algorithm for this problem. This has led to considerable simplifications of the published, quite sophisticated algorithm. Moreover, we can prove that the mentioned algorithm could be quite efficient in practial situations.</abstract><relatedItem type="host"><titleInfo><title>Frontiers in Algorithmics</title><subTitle>Second Annual International Workshop, FAW 2008, Changsha, China, June 19-21, 2008, Proceeedings</subTitle></titleInfo><name type="personal"><namePart type="given">Franco</namePart><namePart type="given">P.</namePart><namePart type="family">Preparata</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Xiaodong</namePart><namePart type="family">Wu</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jianping</namePart><namePart type="family">Yin</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I1701X">Numeric Computing</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic><topic authority="SpringerSubjectCodes" authorityURI="I23050">Computational Biology/Bioinformatics</topic><topic authority="SpringerSubjectCodes" authorityURI="M14018">Algorithms</topic></subject><identifier type="DOI">10.1007/978-3-540-69311-6</identifier><identifier type="ISBN">978-3-540-69310-9</identifier><identifier type="eISBN">978-3-540-69311-6</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">162354</identifier><identifier type="BookID">978-3-540-69311-6</identifier><identifier type="BookChapterCount">35</identifier><identifier type="BookVolumeNumber">5059</identifier><identifier type="BookSequenceNumber">5059</identifier><part><date>2008</date><detail type="volume"><number>5059</number><caption>vol.</caption></detail><extent unit="pages"><start>67</start><end>78</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2008</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></relatedItem><identifier type="istex">117BD01AE315E38544A1808002A02C13AA8EF8CA</identifier><identifier type="DOI">10.1007/978-3-540-69311-6_10</identifier><identifier type="ChapterID">10</identifier><identifier type="ChapterID">Chap10</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2008</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2008</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001693 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001693 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:117BD01AE315E38544A1808002A02C13AA8EF8CA
|texte= Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations
}}
| This area was generated with Dilib version V0.6.31. |  |