Efficient and Practical Algorithms for Sequential Modular Decomposition
Identifieur interne : 009352 ( Main/Exploration ); précédent : 009351; suivant : 009353Efficient and Practical Algorithms for Sequential Modular Decomposition
Auteurs : Elias Dahlhaus [Allemagne] ; Jens Gustedt [France] ; Ross M. McconnellSource :
- Journal of Algorithms [ 0196-6774 ] ; 2001.
Descripteurs français
- Pascal (Inist)
- mix :
English descriptors
- KwdEn :
- Teeft :
- Active edges, Active neighbor, Active neighbors, Adjacency lists, Algorithm, Assembly step, Basic block, Basic blocks, Bipartite graph, Circular list, Comput, Computer science, Congruence partition, Dahlhaus, Data structure, Data structures, Decomposition, Decomposition algorithm, Decomposition tree, Degenerate, Degenerate node, Discrete math, Ehrenfeucht, Gustedt, Habib, Inductive, Inductive step, Internal node, Leaf descendants, Lemma algorithm, Linear time, Maximal module, Mcconnell, Modular, Modular decomposition, Modular decomposition algorithm, Modular decompositions, Module, Modules step, Nding, Node, Other members, Parent pointer, Parent pointers, Partition, Partition class, Partition classes, Partitioning, Pointer, Preorder, Preorder number, Preprocessing, Preprocessing step, Primary sort, Proper subsets, Quotient, Radix, Recency, Recursion, Recursion tree, Recursive, Recursively, Restriction step, Sequential, Sibling, Spinrad, Strong module, Strong modules, Strong neighbor, Subordinate tree, Subset, Substitution decomposition, Tarjan, Topological sort, Tree node, Tree nodes, Undeleted, Undeleted children, Undirected graph, Vertex partitioning, Weak neighbors.
Abstract
Abstract: A module of an undirected graph G=(V,E) is a set X of vertices that have the same set of neighbors in V\X. The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an O(n+mα(m,n)) time bound and a variant with a linear time bound.
Url:
DOI: 10.1006/jagm.2001.1185
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000A06
- to stream Istex, to step Curation: 000A00
- to stream Istex, to step Checkpoint: 001E94
- to stream Main, to step Merge: 009874
- to stream Hal, to step Corpus: 001E91
- to stream Hal, to step Curation: 001E91
- to stream Hal, to step Checkpoint: 005E36
- to stream Main, to step Merge: 009C45
- to stream PascalFrancis, to step Corpus: 000889
- to stream PascalFrancis, to step Curation: 000163
- to stream PascalFrancis, to step Checkpoint: 000906
- to stream Main, to step Merge: 009989
- to stream Main, to step Curation: 009352
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient and Practical Algorithms for Sequential Modular Decomposition</title>
<author><name sortKey="Dahlhaus, Elias" sort="Dahlhaus, Elias" uniqKey="Dahlhaus E" first="Elias" last="Dahlhaus">Elias Dahlhaus</name>
</author>
<author><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name>
</author>
<author><name sortKey="Mcconnell, Ross M" sort="Mcconnell, Ross M" uniqKey="Mcconnell R" first="Ross M" last="Mcconnell">Ross M. Mcconnell</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:2B312D136D8B44D49ED167F1E0FC86882A71AC7C</idno>
<date when="2001" year="2001">2001</date>
<idno type="doi">10.1006/jagm.2001.1185</idno>
<idno type="url">https://api.istex.fr/ark:/67375/6H6-VXX8RP4R-N/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000A06</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000A06</idno>
<idno type="wicri:Area/Istex/Curation">000A00</idno>
<idno type="wicri:Area/Istex/Checkpoint">001E94</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001E94</idno>
<idno type="wicri:doubleKey">0196-6774:2001:Dahlhaus E:efficient:and:practical</idno>
<idno type="wicri:Area/Main/Merge">009874</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00100822</idno>
<idno type="url">https://hal.inria.fr/inria-00100822</idno>
<idno type="wicri:Area/Hal/Corpus">001E91</idno>
<idno type="wicri:Area/Hal/Curation">001E91</idno>
<idno type="wicri:Area/Hal/Checkpoint">005E36</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">005E36</idno>
<idno type="wicri:doubleKey">0196-6774:2001:Dahlhaus E:efficient:and:practical</idno>
<idno type="wicri:Area/Main/Merge">009C45</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:02-0139077</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000889</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000163</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000906</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000906</idno>
<idno type="wicri:doubleKey">0196-6774:2001:Dahlhaus E:efficient:and:practical</idno>
<idno type="wicri:Area/Main/Merge">009989</idno>
<idno type="wicri:Area/Main/Curation">009352</idno>
<idno type="wicri:Area/Main/Exploration">009352</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Efficient and Practical Algorithms for Sequential Modular Decomposition</title>
<author><name sortKey="Dahlhaus, Elias" sort="Dahlhaus, Elias" uniqKey="Dahlhaus E" first="Elias" last="Dahlhaus">Elias Dahlhaus</name>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
<wicri:regionArea>Department of Computer Science and Department of Mathematics, University of Cologne, Cologne</wicri:regionArea>
<wicri:noRegion>Cologne</wicri:noRegion>
<wicri:noRegion>Cologne</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name>
<affiliation wicri:level="3"><country wicri:rule="url">France</country>
<wicri:regionArea>LORIA and INRIA Lorraine, campus scientifique, BP 239, 54506, Vanduvre lés Nancy</wicri:regionArea>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vanduvre lés Nancy</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Mcconnell, Ross M" sort="Mcconnell, Ross M" uniqKey="Mcconnell R" first="Ross M" last="Mcconnell">Ross M. Mcconnell</name>
<affiliation><wicri:noCountry code="subField">rmcconne@carbon.cudenver.eduf3</wicri:noCountry>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Journal of Algorithms</title>
<title level="j" type="abbrev">YJAGM</title>
<idno type="ISSN">0196-6774</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="2001">2001</date>
<biblScope unit="volume">41</biblScope>
<biblScope unit="issue">2</biblScope>
<biblScope unit="page" from="360">360</biblScope>
<biblScope unit="page" to="387">387</biblScope>
</imprint>
<idno type="ISSN">0196-6774</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0196-6774</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Congruence</term>
<term>Efficiency</term>
<term>Graph decomposition</term>
<term>Graph theory</term>
<term>Lower bound</term>
<term>Modular construction</term>
<term>Partition</term>
<term>Sequential decomposition</term>
<term>Sequential extraction</term>
<term>Subgraph</term>
<term>Time complexity</term>
<term>Upper bound</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Algorithme</term>
<term>Borne inférieure</term>
<term>Borne supérieure</term>
<term>Complexité temps</term>
<term>Congruence</term>
<term>Construction modulaire</term>
<term>Décomposition graphe</term>
<term>Décomposition séquentielle</term>
<term>Efficacité</term>
<term>Extraction séquentielle</term>
<term>Partition</term>
<term>Sous graphe</term>
<term>Théorie graphe</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Active edges</term>
<term>Active neighbor</term>
<term>Active neighbors</term>
<term>Adjacency lists</term>
<term>Algorithm</term>
<term>Assembly step</term>
<term>Basic block</term>
<term>Basic blocks</term>
<term>Bipartite graph</term>
<term>Circular list</term>
<term>Comput</term>
<term>Computer science</term>
<term>Congruence partition</term>
<term>Dahlhaus</term>
<term>Data structure</term>
<term>Data structures</term>
<term>Decomposition</term>
<term>Decomposition algorithm</term>
<term>Decomposition tree</term>
<term>Degenerate</term>
<term>Degenerate node</term>
<term>Discrete math</term>
<term>Ehrenfeucht</term>
<term>Gustedt</term>
<term>Habib</term>
<term>Inductive</term>
<term>Inductive step</term>
<term>Internal node</term>
<term>Leaf descendants</term>
<term>Lemma algorithm</term>
<term>Linear time</term>
<term>Maximal module</term>
<term>Mcconnell</term>
<term>Modular</term>
<term>Modular decomposition</term>
<term>Modular decomposition algorithm</term>
<term>Modular decompositions</term>
<term>Module</term>
<term>Modules step</term>
<term>Nding</term>
<term>Node</term>
<term>Other members</term>
<term>Parent pointer</term>
<term>Parent pointers</term>
<term>Partition</term>
<term>Partition class</term>
<term>Partition classes</term>
<term>Partitioning</term>
<term>Pointer</term>
<term>Preorder</term>
<term>Preorder number</term>
<term>Preprocessing</term>
<term>Preprocessing step</term>
<term>Primary sort</term>
<term>Proper subsets</term>
<term>Quotient</term>
<term>Radix</term>
<term>Recency</term>
<term>Recursion</term>
<term>Recursion tree</term>
<term>Recursive</term>
<term>Recursively</term>
<term>Restriction step</term>
<term>Sequential</term>
<term>Sibling</term>
<term>Spinrad</term>
<term>Strong module</term>
<term>Strong modules</term>
<term>Strong neighbor</term>
<term>Subordinate tree</term>
<term>Subset</term>
<term>Substitution decomposition</term>
<term>Tarjan</term>
<term>Topological sort</term>
<term>Tree node</term>
<term>Tree nodes</term>
<term>Undeleted</term>
<term>Undeleted children</term>
<term>Undirected graph</term>
<term>Vertex partitioning</term>
<term>Weak neighbors</term>
</keywords>
<keywords scheme="mix" xml:lang="fr"><term>algorithmes linéaires</term>
<term>décomposition modulaire</term>
<term>linear time algorithms</term>
<term>modular decomposition</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: A module of an undirected graph G=(V,E) is a set X of vertices that have the same set of neighbors in V\X. The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an O(n+mα(m,n)) time bound and a variant with a linear time bound.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Vanduvre lés Nancy</li>
</settlement>
</list>
<tree><noCountry><name sortKey="Mcconnell, Ross M" sort="Mcconnell, Ross M" uniqKey="Mcconnell R" first="Ross M" last="Mcconnell">Ross M. Mcconnell</name>
</noCountry>
<country name="Allemagne"><noRegion><name sortKey="Dahlhaus, Elias" sort="Dahlhaus, Elias" uniqKey="Dahlhaus E" first="Elias" last="Dahlhaus">Elias Dahlhaus</name>
</noRegion>
</country>
<country name="France"><region name="Grand Est"><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name>
</region>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 009352 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 009352 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:2B312D136D8B44D49ED167F1E0FC86882A71AC7C |texte= Efficient and Practical Algorithms for Sequential Modular Decomposition }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |