Design and Implementation of Efficient Data Types for Static Graphs
Identifieur interne : 000E29 ( Istex/Corpus ); précédent : 000E28; suivant : 000E30Design and Implementation of Efficient Data Types for Static Graphs
Auteurs : Stefan N Her ; Oliver ZlotowskiSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2002.
Abstract
Abstract: The LEDA library contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. In this paper we present a design and an implementation of a family of special and ef ficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA’s standard graph type without changing the existing code.
Url:
DOI: 10.1007/3-540-45749-6_65
Links to Exploration step
ISTEX:99FF9B9E166721974CFCC519D38C1E1B7485F956Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Design and Implementation of Efficient Data Types for Static Graphs</title><author><name sortKey="N Her, Stefan" sort="N Her, Stefan" uniqKey="N Her S" first="Stefan" last="N Her">Stefan N Her</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: naeher@informatik.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Zlotowski, Oliver" sort="Zlotowski, Oliver" uniqKey="Zlotowski O" first="Oliver" last="Zlotowski">Oliver Zlotowski</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: zlotowski@informatik.uni-trier.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:99FF9B9E166721974CFCC519D38C1E1B7485F956</idno><date when="2002" year="2002">2002</date><idno type="doi">10.1007/3-540-45749-6_65</idno><idno type="url">https://api.istex.fr/document/99FF9B9E166721974CFCC519D38C1E1B7485F956/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000E29</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000E29</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Design and Implementation of Efficient Data Types for Static Graphs</title><author><name sortKey="N Her, Stefan" sort="N Her, Stefan" uniqKey="N Her S" first="Stefan" last="N Her">Stefan N Her</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: naeher@informatik.uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Zlotowski, Oliver" sort="Zlotowski, Oliver" uniqKey="Zlotowski O" first="Oliver" last="Zlotowski">Oliver Zlotowski</name><affiliation><mods:affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: zlotowski@informatik.uni-trier.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2002</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">99FF9B9E166721974CFCC519D38C1E1B7485F956</idno><idno type="DOI">10.1007/3-540-45749-6_65</idno><idno type="ChapterID">65</idno><idno type="ChapterID">Chap65</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: The LEDA library contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. In this paper we present a design and an implementation of a family of special and ef ficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA’s standard graph type without changing the existing code.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Stefan Näher</name><affiliations><json:string>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</json:string><json:string>E-mail: naeher@informatik.uni-trier.de</json:string></affiliations></json:item><json:item><name>Oliver Zlotowski</name><affiliations><json:string>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</json:string><json:string>E-mail: zlotowski@informatik.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: The LEDA library contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. In this paper we present a design and an implementation of a family of special and ef ficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA’s standard graph type without changing the existing code.</abstract><qualityIndicators><score>5.225</score><pdfVersion>1.3</pdfVersion><pdfPageSize>639 x 792 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>630</abstractCharCount><pdfWordCount>4001</pdfWordCount><pdfCharCount>23740</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>102</abstractWordCount></qualityIndicators><title>Design and Implementation of Efficient Data Types for Static Graphs</title><chapterId><json:string>65</json:string><json:string>Chap65</json:string></chapterId><refBibs><json:item><host><pages><first>758</first></pages><author><json:item><name>Andrew,V Goldberg</name></json:item></author></host></json:item><json:item><host><pages><first>757</first></pages><author></author><title>Dimacs implementation file format</title></host></json:item><json:item><author><json:item><name>B,V Cherkassky</name></json:item><json:item><name>A,V Goldberg</name></json:item></author><host><pages><last>410</last><first>390</first></pages><author></author><title>Algorithmica</title><publicationDate>1997</publicationDate></host><title>On Implementing Push-Relabel Method for the Maximum Flow Problem</title><publicationDate>1997</publicationDate></json:item><json:item><author><json:item><name>A,V Goldberg</name></json:item><json:item><name>R,E Tarjan</name></json:item></author><host><pages><last>146</last><first>136</first></pages><author></author><title>ACM Symposium on Theory of Computing</title><publicationDate>1986</publicationDate></host><title>A New Approach to the Maximum Flow Problem</title><publicationDate>1986</publicationDate></json:item><json:item><host><author><json:item><name>Dietmar Kühl</name></json:item></author><title>Design patterns for the implementation of graph algorithms</title><publicationDate>0755</publicationDate></host></json:item><json:item><host><pages><first>754</first></pages><author><json:item><name>K Mehlhorn</name></json:item><json:item><name>S Näher</name></json:item><json:item><name>M Seel</name></json:item><json:item><name>C Uhrig</name></json:item></author><title>The LEDA User Manual Version 4.3. Algorithmic Solutions GmbH</title><publicationDate>2001</publicationDate></host></json:item><json:item><author><json:item><name>Kurt Mehlhorn</name></json:item><json:item><name>Stefan Näher</name></json:item></author><host><pages><last>102</last><first>96</first></pages><issue>38</issue><author></author><title>Communications of the ACM</title><publicationDate>1995</publicationDate></host><title>Leda: a library of efficient data structures and algorithms</title><publicationDate>1995</publicationDate></json:item><json:item><host><pages><last>758</last><first>756</first></pages><author><json:item><name>Kurt Mehlhorn</name></json:item><json:item><name>Stefan Näher</name></json:item></author><title>LEDA: A Platform for Combinatorial and Geometric Computing</title><publicationDate>1999</publicationDate></host></json:item><json:item><host><pages><first>758</first></pages><author><json:item><name>Jeremy,G Siek</name></json:item><json:item><name>Lie-Quan Lee</name></json:item><json:item><name>Andrew Lumsdaine</name></json:item></author><title>The Boost Graph Library</title><publicationDate>2001</publicationDate></host></json:item><json:item><author><json:item><name>O Zlotowski</name></json:item><json:item><name>M Bäsken</name></json:item></author><host><pages><first>759</first></pages><author></author><title>CGAL User Workshop</title><publicationDate>2002</publicationDate></host><title>An experimental comparision of two-dimensional triangulation packages</title><publicationDate>2002</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><title>Lecture Notes in Computer Science</title><copyrightDate>2002</copyrightDate></serie><host><editor><json:item><name>Rolf Möhring</name><affiliations><json:string>Fakultät II: Mathematik und Naturwissenschaften, Technische Universität Berlin, Strasse des 17. Juni 136, 10623, Berlin, Germany</json:string><json:string>E-mail: moehring@math.tu-berlin.de</json:string></affiliations></json:item><json:item><name>Rajeev Raman</name><affiliations><json:string>Department of Mathematics and Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK</json:string><json:string>E-mail: r.raman@mcs.le.ac.uk</json:string></affiliations></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>Data Structures</value></json:item><json:item><value>Computer Graphics</value></json:item><json:item><value>Algorithms</value></json:item></subject><isbn><json:string>978-3-540-44180-9</json:string></isbn><language><json:string>unknown</json:string></language><title>Algorithms — ESA 2002</title><bookId><json:string>3-540-45749-6</json:string></bookId><volume>2461</volume><pages><last>759</last><first>748</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-45749-7</json:string></eisbn><copyrightDate>2002</copyrightDate><doi><json:string>10.1007/3-540-45749-6</json:string></doi></host><publicationDate>2002</publicationDate><copyrightDate>2002</copyrightDate><doi><json:string>10.1007/3-540-45749-6_65</json:string></doi><id>99FF9B9E166721974CFCC519D38C1E1B7485F956</id><score>0.6498643</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/99FF9B9E166721974CFCC519D38C1E1B7485F956/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/99FF9B9E166721974CFCC519D38C1E1B7485F956/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/99FF9B9E166721974CFCC519D38C1E1B7485F956/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Design and Implementation of Efficient Data Types for Static Graphs</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, 2002</p></availability><date>2002</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Design and Implementation of Efficient Data Types for Static Graphs</title><author xml:id="author-1"><persName><forename type="first">Stefan</forename><surname>Näher</surname></persName><email>naeher@informatik.uni-trier.de</email><affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</affiliation></author><author xml:id="author-2"><persName><forename type="first">Oliver</forename><surname>Zlotowski</surname></persName><email>zlotowski@informatik.uni-trier.de</email><affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</affiliation></author></analytic><monogr><title level="m">Algorithms — ESA 2002</title><title level="m" type="sub">10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings</title><idno type="pISBN">978-3-540-44180-9</idno><idno type="eISBN">978-3-540-45749-7</idno><idno type="pISSN">0302-9743</idno><idno type="DOI">10.1007/3-540-45749-6</idno><idno type="book-ID">3-540-45749-6</idno><idno type="book-title-ID">72485</idno><idno type="book-sequence-number">2461</idno><idno type="book-volume-number">2461</idno><idno type="book-chapter-count">78</idno><editor><persName><forename type="first">Rolf</forename><surname>Möhring</surname></persName><email>moehring@math.tu-berlin.de</email><affiliation>Fakultät II: Mathematik und Naturwissenschaften, Technische Universität Berlin, Strasse des 17. Juni 136, 10623, Berlin, Germany</affiliation></editor><editor><persName><forename type="first">Rajeev</forename><surname>Raman</surname></persName><email>r.raman@mcs.le.ac.uk</email><affiliation>Department of Mathematics and Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2002-08-29"></date><biblScope unit="volume">2461</biblScope><biblScope unit="page" from="748">748</biblScope><biblScope unit="page" to="759">759</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>2002</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="series-Id">558</idno></series><idno type="istex">99FF9B9E166721974CFCC519D38C1E1B7485F956</idno><idno type="DOI">10.1007/3-540-45749-6_65</idno><idno type="ChapterID">65</idno><idno type="ChapterID">Chap65</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2002</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: The LEDA library contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. In this paper we present a design and an implementation of a family of special and ef ficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA’s standard graph type without changing the existing code.</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>I15017</label><label>I22013</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>Data Structures</term></item><item><term>Computer Graphics</term></item><item><term>Algorithms</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2002-08-29">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-23">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-21">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/99FF9B9E166721974CFCC519D38C1E1B7485F956/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 TocLevels="0" SeriesType="Series"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo Language="En" TocLevels="0" NumberingStyle="Unnumbered" BookProductType="Proceedings" MediaType="eBook"><BookID>3-540-45749-6</BookID><BookTitle>Algorithms — ESA 2002</BookTitle><BookSubTitle>10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings</BookSubTitle><BookVolumeNumber>2461</BookVolumeNumber><BookSequenceNumber>2461</BookSequenceNumber><BookDOI>10.1007/3-540-45749-6</BookDOI><BookTitleID>72485</BookTitleID><BookPrintISBN>978-3-540-44180-9</BookPrintISBN><BookElectronicISBN>978-3-540-45749-7</BookElectronicISBN><BookChapterCount>78</BookChapterCount><BookHistory><OnlineDate><Year>2002</Year><Month>8</Month><Day>29</Day></OnlineDate></BookHistory><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2002</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="I15017" Priority="4" Type="Secondary">Data Structures</BookSubject><BookSubject Code="I22013" Priority="5" Type="Secondary">Computer Graphics</BookSubject><BookSubject Code="M14018" Priority="6" Type="Secondary">Algorithms</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Rolf</GivenName><FamilyName>Möhring</FamilyName></EditorName><Contact><Email>moehring@math.tu-berlin.de</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Rajeev</GivenName><FamilyName>Raman</FamilyName></EditorName><Contact><Email>r.raman@mcs.le.ac.uk</Email></Contact></Editor><Affiliation ID="Aff4"><OrgDivision>Fakultät II: Mathematik und Naturwissenschaften</OrgDivision><OrgName>Technische Universität Berlin</OrgName><OrgAddress><Street>Strasse des 17. Juni 136</Street><Postcode>10623</Postcode><City>Berlin</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>Department of Mathematics and Computer Science</OrgDivision><OrgName>University of Leicester</OrgName><OrgAddress><Street>University Road</Street><Postcode>LE1 7RH</Postcode><City>Leicester</City><Country>UK</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part2"><PartInfo TocLevels="0"><PartID>2</PartID><PartSequenceNumber>2</PartSequenceNumber><PartTitle>Contributed Papers</PartTitle><PartChapterCount>74</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookID>3-540-45749-6</BookID><BookTitle>Algorithms — ESA 2002</BookTitle></PartContext></PartInfo><Chapter ID="Chap65" Language="En"><ChapterInfo ChapterType="OriginalPaper" NumberingStyle="Unnumbered" Language="En" TocLevels="0" ContainsESM="No"><ChapterID>65</ChapterID><ChapterDOI>10.1007/3-540-45749-6_65</ChapterDOI><ChapterSequenceNumber>65</ChapterSequenceNumber><ChapterTitle Language="En">Design and Implementation of Efficient Data Types for Static Graphs</ChapterTitle><ChapterFirstPage>748</ChapterFirstPage><ChapterLastPage>759</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2002</CopyrightYear></ChapterCopyright><ChapterHistory><RegistrationDate><Year>2002</Year><Month>8</Month><Day>28</Day></RegistrationDate><OnlineDate><Year>2002</Year><Month>8</Month><Day>29</Day></OnlineDate></ChapterHistory><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><PartID>2</PartID><BookID>3-540-45749-6</BookID><BookTitle>Algorithms — ESA 2002</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Stefan</GivenName><FamilyName>Näher</FamilyName></AuthorName><Contact><Email>naeher@informatik.uni-trier.de</Email></Contact></Author><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Oliver</GivenName><FamilyName>Zlotowski</FamilyName></AuthorName><Contact><Email>zlotowski@informatik.uni-trier.de</Email></Contact></Author><Affiliation ID="Aff6"><OrgDivision>Fachbereich IV - Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postcode>54296</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>The LEDA library contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. In this paper we present a design and an implementation of a family of special and ef ficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA’s standard graph type without changing the existing code.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This work was supported in part by DFG-Grant Na 303/1-2, Forschungsschwerpunkt “Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen”.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Design and Implementation of Efficient Data Types for Static Graphs</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Design and Implementation of Efficient Data Types for Static Graphs</title></titleInfo><name type="personal"><namePart type="given">Stefan</namePart><namePart type="family">Näher</namePart><affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</affiliation><affiliation>E-mail: naeher@informatik.uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Oliver</namePart><namePart type="family">Zlotowski</namePart><affiliation>Fachbereich IV - Informatik, Universität Trier, 54296, Trier, Germany</affiliation><affiliation>E-mail: zlotowski@informatik.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">2002-08-29</dateIssued><copyrightDate encoding="w3cdtf">2002</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: The LEDA library contains a very general and powerful graph type. This type provides the operations for all graphs of the library in one single interface. In many situations, however, this general interface is not needed and more specialized implementations of graphs could be used to improve the efficiency of graph algorithms. In this paper we present a design and an implementation of a family of special and ef ficient static graph types which fit into the LEDA environment of graphs and algorithms. They allow to speed up existing programs written with LEDA’s standard graph type without changing the existing code.</abstract><relatedItem type="host"><titleInfo><title>Algorithms — ESA 2002</title><subTitle>10th Annual European Symposium Rome, Italy, September 17–21, 2002 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Rolf</namePart><namePart type="family">Möhring</namePart><affiliation>Fakultät II: Mathematik und Naturwissenschaften, Technische Universität Berlin, Strasse des 17. Juni 136, 10623, Berlin, Germany</affiliation><affiliation>E-mail: moehring@math.tu-berlin.de</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Rajeev</namePart><namePart type="family">Raman</namePart><affiliation>Department of Mathematics and Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK</affiliation><affiliation>E-mail: r.raman@mcs.le.ac.uk</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2002</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="I15017">Data Structures</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic><topic authority="SpringerSubjectCodes" authorityURI="M14018">Algorithms</topic></subject><identifier type="DOI">10.1007/3-540-45749-6</identifier><identifier type="ISBN">978-3-540-44180-9</identifier><identifier type="eISBN">978-3-540-45749-7</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="BookTitleID">72485</identifier><identifier type="BookID">3-540-45749-6</identifier><identifier type="BookChapterCount">78</identifier><identifier type="BookVolumeNumber">2461</identifier><identifier type="BookSequenceNumber">2461</identifier><identifier type="PartChapterCount">74</identifier><part><date>2002</date><detail type="part"><title>Contributed Papers</title></detail><detail type="volume"><number>2461</number><caption>vol.</caption></detail><extent unit="pages"><start>748</start><end>759</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2002</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2002</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2002</recordOrigin></recordInfo></relatedItem><identifier type="istex">99FF9B9E166721974CFCC519D38C1E1B7485F956</identifier><identifier type="DOI">10.1007/3-540-45749-6_65</identifier><identifier type="ChapterID">65</identifier><identifier type="ChapterID">Chap65</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2002</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2002</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 000E29 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000E29 | 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:99FF9B9E166721974CFCC519D38C1E1B7485F956
|texte= Design and Implementation of Efficient Data Types for Static Graphs
}}
| This area was generated with Dilib version V0.6.31. |  |