A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
Identifieur interne : 001B88 ( Istex/Corpus ); précédent : 001B87; suivant : 001B89A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
Auteurs : Binh-Minh Bui-Xuan ; Pinar Heggernes ; Daniel Meister ; Andrzej ProskurowskiSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
Abstract
Abstract: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.
Url:
DOI: 10.1007/978-3-642-22685-4_30
Links to Exploration step
ISTEX:E0D5AC59000A21FA35884564DF9E64538F6ECD66Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title><author><name sortKey="Bui Xuan, Binh Minh" sort="Bui Xuan, Binh Minh" uniqKey="Bui Xuan B" first="Binh-Minh" last="Bui-Xuan">Binh-Minh Bui-Xuan</name><affiliation><mods:affiliation>Department of Informatics, University of Bergen, Norway</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: buixuan@ii.uib.no</mods:affiliation></affiliation></author><author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name><affiliation><mods:affiliation>Department of Informatics, University of Bergen, Norway</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: pinar.heggernes@ii.uib.no</mods:affiliation></affiliation></author><author><name sortKey="Meister, Daniel" sort="Meister, Daniel" uniqKey="Meister D" first="Daniel" last="Meister">Daniel Meister</name><affiliation><mods:affiliation>Theoretical Computer Science, University of Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: daniel.meister@uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Proskurowski, Andrzej" sort="Proskurowski, Andrzej" uniqKey="Proskurowski A" first="Andrzej" last="Proskurowski">Andrzej Proskurowski</name><affiliation><mods:affiliation>Department of Information and Computer Science, University of Oregon, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: andrzej@cs.uoregon.edu</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:E0D5AC59000A21FA35884564DF9E64538F6ECD66</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-22685-4_30</idno><idno type="url">https://api.istex.fr/document/E0D5AC59000A21FA35884564DF9E64538F6ECD66/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001B88</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001B88</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title><author><name sortKey="Bui Xuan, Binh Minh" sort="Bui Xuan, Binh Minh" uniqKey="Bui Xuan B" first="Binh-Minh" last="Bui-Xuan">Binh-Minh Bui-Xuan</name><affiliation><mods:affiliation>Department of Informatics, University of Bergen, Norway</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: buixuan@ii.uib.no</mods:affiliation></affiliation></author><author><name sortKey="Heggernes, Pinar" sort="Heggernes, Pinar" uniqKey="Heggernes P" first="Pinar" last="Heggernes">Pinar Heggernes</name><affiliation><mods:affiliation>Department of Informatics, University of Bergen, Norway</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: pinar.heggernes@ii.uib.no</mods:affiliation></affiliation></author><author><name sortKey="Meister, Daniel" sort="Meister, Daniel" uniqKey="Meister D" first="Daniel" last="Meister">Daniel Meister</name><affiliation><mods:affiliation>Theoretical Computer Science, University of Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: daniel.meister@uni-trier.de</mods:affiliation></affiliation></author><author><name sortKey="Proskurowski, Andrzej" sort="Proskurowski, Andrzej" uniqKey="Proskurowski A" first="Andrzej" last="Proskurowski">Andrzej Proskurowski</name><affiliation><mods:affiliation>Department of Information and Computer Science, University of Oregon, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: andrzej@cs.uoregon.edu</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2011</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">E0D5AC59000A21FA35884564DF9E64538F6ECD66</idno><idno type="DOI">10.1007/978-3-642-22685-4_30</idno><idno type="ChapterID">30</idno><idno type="ChapterID">Chap30</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: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Binh-Minh Bui-Xuan</name><affiliations><json:string>Department of Informatics, University of Bergen, Norway</json:string><json:string>E-mail: buixuan@ii.uib.no</json:string></affiliations></json:item><json:item><name>Pinar Heggernes</name><affiliations><json:string>Department of Informatics, University of Bergen, Norway</json:string><json:string>E-mail: pinar.heggernes@ii.uib.no</json:string></affiliations></json:item><json:item><name>Daniel Meister</name><affiliations><json:string>Theoretical Computer Science, University of Trier, Germany</json:string><json:string>E-mail: daniel.meister@uni-trier.de</json:string></affiliations></json:item><json:item><name>Andrzej Proskurowski</name><affiliations><json:string>Department of Information and Computer Science, University of Oregon, USA</json:string><json:string>E-mail: andrzej@cs.uoregon.edu</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.</abstract><qualityIndicators><score>9.236</score><pdfVersion>1.6</pdfVersion><pdfPageSize>429.442 x 659.895 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>1459</abstractCharCount><pdfWordCount>5670</pdfWordCount><pdfCharCount>26591</pdfCharCount><pdfPageCount>12</pdfPageCount><abstractWordCount>228</abstractWordCount></qualityIndicators><title>A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title><chapterId><json:string>30</json:string><json:string>Chap30</json:string></chapterId><refBibs><json:item><host><author><json:item><name>A Bernáth</name></json:item></author><title>A note on the directed source location algorithm</title><publicationDate>2004</publicationDate></host></json:item><json:item><host><author><json:item><name>B.-M Bui-Xuan</name></json:item></author><title>Tree-representation of set families in graph decompositions and efficient algorithms</title><publicationDate>2008</publicationDate></host></json:item><json:item><author><json:item><name>B.-M Bui-Xuan</name></json:item><json:item><name>M Habib</name></json:item></author><host><volume>4957</volume><pages><last>503</last><first>492</first></pages><author></author><title>LNCS</title><publicationDate>2008</publicationDate></host><title>A representation theorem for union-difference families and application</title><publicationDate>2008</publicationDate></json:item><json:item><author><json:item><name>B.-M Bui-Xuan</name></json:item><json:item><name>M Habib</name></json:item><json:item><name>V Limouzy</name></json:item><json:item><name>F De Montgolfier</name></json:item></author><host><author></author><title>Algorithmic Aspects of a General Modular Decomposition Theory</title><publicationDate>1993</publicationDate></host><publicationDate>1993</publicationDate></json:item><json:item><author><json:item><name>B.-M Bui-Xuan</name></json:item><json:item><name>M Habib</name></json:item><json:item><name>M Rao</name></json:item></author><host><author></author><title>European Journal of Combinatorics</title></host><title>Tree-representation of set families and applications to combinatorial decompositions</title></json:item><json:item><author><json:item><name>M Chein</name></json:item><json:item><name>M Habib</name></json:item><json:item><name>M.-C Maurer</name></json:item></author><host><volume>37</volume><pages><last>50</last><first>35</first></pages><author></author><title>Discrete Mathematics</title><publicationDate>1981</publicationDate></host><title>Partitive hypergraphs</title><publicationDate>1981</publicationDate></json:item><json:item><host><author><json:item><name>W Cunningham</name></json:item></author><title>A combinatorial decomposition theory</title><publicationDate>1973</publicationDate></host></json:item><json:item><author><json:item><name>W Cunningham</name></json:item><json:item><name>J Edmonds</name></json:item></author><host><volume>32</volume><pages><last>765</last><first>734</first></pages><author></author><title>Canadian Journal of Mathematics</title><publicationDate>1980</publicationDate></host><title>A combinatorial decomposition theory</title><publicationDate>1980</publicationDate></json:item><json:item><author><json:item><name>W Cunningham</name></json:item></author><host><volume>2</volume><pages><last>228</last><first>214</first></pages><author></author><title>SIAM Journal on Algebraic and Discrete Methods</title><publicationDate>1982</publicationDate></host><title>Decomposition of directed graphs</title><publicationDate>1982</publicationDate></json:item><json:item><author><json:item><name>E Dinitz</name></json:item><json:item><name>A Karzanov</name></json:item><json:item><name>M Lomonosov</name></json:item></author><host><pages><last>306</last><first>290</first></pages><author></author><title>Pridman, A. (ed.) Studies in Discrete Optimization</title><publicationDate>1976</publicationDate></host><title>On the structure of a family of minimal weighted cuts in a graph</title><publicationDate>1976</publicationDate></json:item><json:item><author><json:item><name>J Edmonds</name></json:item><json:item><name>R Giles</name></json:item></author><host><volume>1</volume><pages><last>204</last><first>185</first></pages><author></author><title>Annals of Discrete Mathematics</title><publicationDate>1977</publicationDate></host><title>A min-max relation for submodular functions on graphs</title><publicationDate>1977</publicationDate></json:item><json:item><author><json:item><name>H Gabow</name></json:item></author><host><volume>18</volume><pages><last>628</last><first>586</first></pages><author></author><title>Journal of Algorithms</title><publicationDate>1995</publicationDate></host><title>Centroids, Representations, and Submoduar Flows</title><publicationDate>1995</publicationDate></json:item><json:item><author><json:item><name>W.-L Hsu</name></json:item><json:item><name>C Gabor</name></json:item><json:item><name>K Supowit</name></json:item></author><host><volume>36</volume><pages><last>473</last><first>435</first></pages><author></author><title>Journal of the ACM</title><publicationDate>1989</publicationDate></host><title>Recognizing circle graphs in polynomial time</title><publicationDate>1989</publicationDate></json:item><json:item><author><json:item><name>F De Mongolfier</name></json:item><json:item><name>M Rao</name></json:item></author><host><volume>22</volume><pages><last>177</last><first>173</first></pages><author></author><title>Electronic Notes in Discrete Mathematics</title><publicationDate>2005</publicationDate></host><title>The bi-join decomposition</title><publicationDate>2005</publicationDate></json:item><json:item><author><json:item><name>M Queyranne</name></json:item></author><host><volume>82</volume><pages><last>12</last><first>3</first></pages><author></author><title>Mathematical Programming</title><publicationDate>1998</publicationDate></host><title>Minimizing symmetric submodular functions</title><publicationDate>1998</publicationDate></json:item><json:item><host><author><json:item><name>A Schrijver</name></json:item></author><title>Combinatorial Optimization – Polyhedra and Efficiency</title><publicationDate>2003</publicationDate></host></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>David Hutchison</name><affiliations><json:string>Lancaster University, Lancaster, UK</json:string></affiliations></json:item><json:item><name>Takeo Kanade</name><affiliations><json:string>Carnegie Mellon University, Pittsburgh, PA, USA</json:string></affiliations></json:item><json:item><name>Josef Kittler</name><affiliations><json:string>University of Surrey, Guildford, UK</json:string></affiliations></json:item><json:item><name>Jon M. Kleinberg</name><affiliations><json:string>Cornell University, Ithaca, NY, USA</json:string></affiliations></json:item><json:item><name>Friedemann Mattern</name><affiliations><json:string>ETH Zurich, Zurich, Switzerland</json:string></affiliations></json:item><json:item><name>John C. Mitchell</name><affiliations><json:string>Stanford University, Stanford, CA, USA</json:string></affiliations></json:item><json:item><name>Moni Naor</name><affiliations><json:string>Weizmann Institute of Science, Rehovot, Israel</json:string></affiliations></json:item><json:item><name>Oscar Nierstrasz</name><affiliations><json:string>University of Bern, Bern, Switzerland</json:string></affiliations></json:item><json:item><name>C. Pandu Rangan</name><affiliations><json:string>Indian Institute of Technology, Madras, India</json:string></affiliations></json:item><json:item><name>Bernhard Steffen</name><affiliations><json:string>University of Dortmund, Dortmund, Germany</json:string></affiliations></json:item><json:item><name>Madhu Sudan</name><affiliations><json:string>Massachusetts Institute of Technology, MA, USA</json:string></affiliations></json:item><json:item><name>Demetri Terzopoulos</name><affiliations><json:string>University of California, Los Angeles, CA, USA</json:string></affiliations></json:item><json:item><name>Doug Tygar</name><affiliations><json:string>University of California, Berkeley, CA, USA</json:string></affiliations></json:item><json:item><name>Moshe Y. Vardi</name><affiliations><json:string>Rice University, Houston, TX, USA</json:string></affiliations></json:item><json:item><name>Gerhard Weikum</name><affiliations><json:string>Max-Planck Institute of Computer Science, Saarbrücken, Germany</json:string></affiliations></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>2011</copyrightDate></serie><host><editor><json:item><name>Bin Fu</name><affiliations><json:string>Department of Computer Science, University of Texas-Pan American, 78539, Edinburg, TX, USA</json:string><json:string>E-mail: binfu@cs.panam.edu</json:string></affiliations></json:item><json:item><name>Ding-Zhu Du</name><affiliations><json:string>Department of Computer Science, University of Texas at Dallas, 75080, Richardson, TX, USA</json:string><json:string>E-mail: dzdu@utdallas.edu</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>Computer Communication Networks</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Computer Graphics</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item></subject><isbn><json:string>978-3-642-22684-7</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Computing and Combinatorics</title><bookId><json:string>978-3-642-22685-4</json:string></bookId><volume>6842</volume><pages><last>342</last><first>331</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-642-22685-4</json:string></eisbn><copyrightDate>2011</copyrightDate><doi><json:string>10.1007/978-3-642-22685-4</json:string></doi></host><publicationDate>2011</publicationDate><copyrightDate>2011</copyrightDate><doi><json:string>10.1007/978-3-642-22685-4_30</json:string></doi><id>E0D5AC59000A21FA35884564DF9E64538F6ECD66</id><score>0.49900496</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/E0D5AC59000A21FA35884564DF9E64538F6ECD66/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/E0D5AC59000A21FA35884564DF9E64538F6ECD66/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/E0D5AC59000A21FA35884564DF9E64538F6ECD66/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</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 GmbH Berlin Heidelberg, 2011</p></availability><date>2011</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title><author xml:id="author-1"><persName><forename type="first">Binh-Minh</forename><surname>Bui-Xuan</surname></persName><email>buixuan@ii.uib.no</email><affiliation>Department of Informatics, University of Bergen, Norway</affiliation></author><author xml:id="author-2"><persName><forename type="first">Pinar</forename><surname>Heggernes</surname></persName><email>pinar.heggernes@ii.uib.no</email><affiliation>Department of Informatics, University of Bergen, Norway</affiliation></author><author xml:id="author-3"><persName><forename type="first">Daniel</forename><surname>Meister</surname></persName><email>daniel.meister@uni-trier.de</email><affiliation>Theoretical Computer Science, University of Trier, Germany</affiliation></author><author xml:id="author-4"><persName><forename type="first">Andrzej</forename><surname>Proskurowski</surname></persName><email>andrzej@cs.uoregon.edu</email><affiliation>Department of Information and Computer Science, University of Oregon, USA</affiliation></author></analytic><monogr><title level="m">Computing and Combinatorics</title><title level="m" type="sub">17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings</title><idno type="pISBN">978-3-642-22684-7</idno><idno type="eISBN">978-3-642-22685-4</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/978-3-642-22685-4</idno><idno type="book-ID">978-3-642-22685-4</idno><idno type="book-title-ID">272017</idno><idno type="book-sequence-number">6842</idno><idno type="book-volume-number">6842</idno><idno type="book-chapter-count">55</idno><editor><persName><forename type="first">Bin</forename><surname>Fu</surname></persName><email>binfu@cs.panam.edu</email><affiliation>Department of Computer Science, University of Texas-Pan American, 78539, Edinburg, TX, USA</affiliation></editor><editor><persName><forename type="first">Ding-Zhu</forename><surname>Du</surname></persName><email>dzdu@utdallas.edu</email><affiliation>Department of Computer Science, University of Texas at Dallas, 75080, Richardson, TX, USA</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2011"></date><biblScope unit="volume">6842</biblScope><biblScope unit="page" from="331">331</biblScope><biblScope unit="page" to="342">342</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName><affiliation>Lancaster University, Lancaster, UK</affiliation></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName><affiliation>University of Surrey, Guildford, UK</affiliation></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName><affiliation>Cornell University, Ithaca, NY, USA</affiliation></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName><affiliation>ETH Zurich, Zurich, Switzerland</affiliation></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName><affiliation>Stanford University, Stanford, CA, USA</affiliation></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName><affiliation>University of Bern, Bern, Switzerland</affiliation></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName><affiliation>Indian Institute of Technology, Madras, India</affiliation></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName><affiliation>University of Dortmund, Dortmund, Germany</affiliation></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName><affiliation>University of California, Los Angeles, CA, USA</affiliation></editor><editor><persName><forename type="first">Doug</forename><surname>Tygar</surname></persName><affiliation>University of California, Berkeley, CA, USA</affiliation></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName><affiliation>Rice University, Houston, TX, USA</affiliation></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><affiliation>Max-Planck Institute of Computer Science, Saarbrücken, Germany</affiliation></editor><biblScope><date>2011</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">E0D5AC59000A21FA35884564DF9E64538F6ECD66</idno><idno type="DOI">10.1007/978-3-642-22685-4_30</idno><idno type="ChapterID">30</idno><idno type="ChapterID">Chap30</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2011</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.</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>I13022</label><label>I16013</label><label>I22013</label><label>I21017</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>Computer Communication Networks</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Computer Graphics</term></item><item><term>Artificial Intelligence (incl. Robotics)</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2011">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/E0D5AC59000A21FA35884564DF9E64538F6ECD66/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 AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff9"><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff10"><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff11"><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff12"><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff13"><EditorName DisplayOrder="Western"><GivenName>Doug</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff14"><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff15"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Lancaster University</OrgName><OrgAddress><City>Lancaster</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Carnegie Mellon University</OrgName><OrgAddress><City>Pittsburgh</City><State>PA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Surrey</OrgName><OrgAddress><City>Guildford</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Cornell University</OrgName><OrgAddress><City>Ithaca</City><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>ETH Zurich</OrgName><OrgAddress><City>Zurich</City><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgName>Stanford University</OrgName><OrgAddress><City>Stanford</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgName>Weizmann Institute of Science</OrgName><OrgAddress><City>Rehovot</City><Country>Israel</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgName>University of Bern</OrgName><OrgAddress><City>Bern</City><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgName>Indian Institute of Technology</OrgName><OrgAddress><City>Madras</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff10"><OrgName>University of Dortmund</OrgName><OrgAddress><City>Dortmund</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff11"><OrgName>Massachusetts Institute of Technology</OrgName><OrgAddress><State>MA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff12"><OrgName>University of California</OrgName><OrgAddress><City>Los Angeles</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff13"><OrgName>University of California</OrgName><OrgAddress><City>Berkeley</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff14"><OrgName>Rice University</OrgName><OrgAddress><City>Houston</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff15"><OrgName>Max-Planck Institute of Computer Science</OrgName><OrgAddress><City>Saarbrücken</City><Country>Germany</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-642-22685-4</BookID><BookTitle>Computing and Combinatorics</BookTitle><BookSubTitle>17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings</BookSubTitle><BookVolumeNumber>6842</BookVolumeNumber><BookSequenceNumber>6842</BookSequenceNumber><BookDOI>10.1007/978-3-642-22685-4</BookDOI><BookTitleID>272017</BookTitleID><BookPrintISBN>978-3-642-22684-7</BookPrintISBN><BookElectronicISBN>978-3-642-22685-4</BookElectronicISBN><BookChapterCount>55</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag GmbH Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2011</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="I13022" Priority="3" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I16013" Priority="4" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I22013" Priority="5" Type="Secondary">Computer Graphics</BookSubject><BookSubject Code="I21017" Priority="6" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff16"><EditorName DisplayOrder="Western"><GivenName>Bin</GivenName><FamilyName>Fu</FamilyName></EditorName><Contact><Email>binfu@cs.panam.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff17"><EditorName DisplayOrder="Western"><GivenName>Ding-Zhu</GivenName><FamilyName>Du</FamilyName></EditorName><Contact><Email>dzdu@utdallas.edu</Email></Contact></Editor><Affiliation ID="Aff16"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of Texas-Pan American</OrgName><OrgAddress><Postcode>78539</Postcode><City>Edinburg</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff17"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of Texas at Dallas</OrgName><OrgAddress><Postcode>75080</Postcode><City>Richardson</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Chapter ID="Chap30" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>30</ChapterID><ChapterDOI>10.1007/978-3-642-22685-4_30</ChapterDOI><ChapterSequenceNumber>30</ChapterSequenceNumber><ChapterTitle Language="En">A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</ChapterTitle><ChapterFirstPage>331</ChapterFirstPage><ChapterLastPage>342</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2011</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-642-22685-4</BookID><BookTitle>Computing and Combinatorics</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff18"><AuthorName DisplayOrder="Western"><GivenName>Binh-Minh</GivenName><FamilyName>Bui-Xuan</FamilyName></AuthorName><Contact><Email>buixuan@ii.uib.no</Email></Contact></Author><Author AffiliationIDS="Aff18"><AuthorName DisplayOrder="Western"><GivenName>Pinar</GivenName><FamilyName>Heggernes</FamilyName></AuthorName><Contact><Email>pinar.heggernes@ii.uib.no</Email></Contact></Author><Author AffiliationIDS="Aff19"><AuthorName DisplayOrder="Western"><GivenName>Daniel</GivenName><FamilyName>Meister</FamilyName></AuthorName><Contact><Email>daniel.meister@uni-trier.de</Email></Contact></Author><Author AffiliationIDS="Aff20"><AuthorName DisplayOrder="Western"><GivenName>Andrzej</GivenName><FamilyName>Proskurowski</FamilyName></AuthorName><Contact><Email>andrzej@cs.uoregon.edu</Email></Contact></Author><Affiliation ID="Aff18"><OrgDivision>Department of Informatics</OrgDivision><OrgName>University of Bergen</OrgName><OrgAddress><Country>Norway</Country></OrgAddress></Affiliation><Affiliation ID="Aff19"><OrgDivision>Theoretical Computer Science</OrgDivision><OrgName>University of Trier</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff20"><OrgDivision>Department of Information and Computer Science</OrgDivision><OrgName>University of Oregon</OrgName><OrgAddress><Country>USA</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly.</Para><Para>We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an <InlineEquation ID="IEq1"><InlineMediaObject><ImageObject FileRef="978-3-642-22685-4_30_Chapter_TeX2GIF_IEq1.gif" Format="GIF" Color="BlackWhite" Type="Linedraw" Rendition="HTML"></ImageObject></InlineMediaObject><EquationSource Format="TEX">${\cal O}(n^3)$</EquationSource></InlineEquation>-time algorithm for computing a tree representation.</Para></Abstract><ArticleNote Type="Misc"><SimplePara>This work was supported by the Research Council of Norway. The first author was supported by the French National Research Agency, project MAGNUM.</SimplePara></ArticleNote></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition</title></titleInfo><name type="personal"><namePart type="given">Binh-Minh</namePart><namePart type="family">Bui-Xuan</namePart><affiliation>Department of Informatics, University of Bergen, Norway</affiliation><affiliation>E-mail: buixuan@ii.uib.no</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Pinar</namePart><namePart type="family">Heggernes</namePart><affiliation>Department of Informatics, University of Bergen, Norway</affiliation><affiliation>E-mail: pinar.heggernes@ii.uib.no</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Daniel</namePart><namePart type="family">Meister</namePart><affiliation>Theoretical Computer Science, University of Trier, Germany</affiliation><affiliation>E-mail: daniel.meister@uni-trier.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Andrzej</namePart><namePart type="family">Proskurowski</namePart><affiliation>Department of Information and Computer Science, University of Oregon, USA</affiliation><affiliation>E-mail: andrzej@cs.uoregon.edu</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">2011</dateIssued><copyrightDate encoding="w3cdtf">2011</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: A set family is a collection of sets over a universe. If a set family satisfies certain closure properties then it admits an efficient representation of its members by labeled trees. The size of the tree is proportional to the size of the universe, whereas the number of set family members can be exponential. Computing such efficient representations is an important task in algorithm design. Set families are usually not given explicitly (by listing their members) but represented implicitly. We consider the problem of efficiently computing tree representations of set families. Assuming the existence of efficient algorithms for solving the Membership and Separation problems, we prove that if a set family satisfies weak closure properties then there exists an efficient algorithm for computing a tree representation of the set family. The running time of the algorithm will mainly depend on the running times of the algorithms for the two basic problems. Our algorithm generalizes several previous results and provides a unified approach to the computation for a large class of decompositions of graphs. We also introduce a decomposition notion for directed graphs which has no undirected analogue. We show that the results of the first part of the paper are applicable to this new decomposition. Finally, we give efficient algorithms for the two basic problems and obtain an ${\cal O}(n^3)$ -time algorithm for computing a tree representation.</abstract><relatedItem type="host"><titleInfo><title>Computing and Combinatorics</title><subTitle>17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Bin</namePart><namePart type="family">Fu</namePart><affiliation>Department of Computer Science, University of Texas-Pan American, 78539, Edinburg, TX, USA</affiliation><affiliation>E-mail: binfu@cs.panam.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Ding-Zhu</namePart><namePart type="family">Du</namePart><affiliation>Department of Computer Science, University of Texas at Dallas, 75080, Richardson, TX, USA</affiliation><affiliation>E-mail: dzdu@utdallas.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2011</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="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I22013">Computer Graphics</topic><topic authority="SpringerSubjectCodes" authorityURI="I21017">Artificial Intelligence (incl. Robotics)</topic></subject><identifier type="DOI">10.1007/978-3-642-22685-4</identifier><identifier type="ISBN">978-3-642-22684-7</identifier><identifier type="eISBN">978-3-642-22685-4</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">272017</identifier><identifier type="BookID">978-3-642-22685-4</identifier><identifier type="BookChapterCount">55</identifier><identifier type="BookVolumeNumber">6842</identifier><identifier type="BookSequenceNumber">6842</identifier><part><date>2011</date><detail type="volume"><number>6842</number><caption>vol.</caption></detail><extent unit="pages"><start>331</start><end>342</end></extent></part><recordInfo><recordOrigin>Springer-Verlag GmbH Berlin Heidelberg, 2011</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><affiliation>Lancaster University, Lancaster, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><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><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Zurich, Switzerland</affiliation><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><affiliation>Stanford University, Stanford, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>University of California, Los Angeles, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Doug</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><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><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbrücken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2011</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 GmbH Berlin Heidelberg, 2011</recordOrigin></recordInfo></relatedItem><identifier type="istex">E0D5AC59000A21FA35884564DF9E64538F6ECD66</identifier><identifier type="DOI">10.1007/978-3-642-22685-4_30</identifier><identifier type="ChapterID">30</identifier><identifier type="ChapterID">Chap30</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag GmbH Berlin Heidelberg, 2011</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2011</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 001B88 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001B88 | 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:E0D5AC59000A21FA35884564DF9E64538F6ECD66
|texte= A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
}}
| This area was generated with Dilib version V0.6.31. |  |