Efficient and Practical Algorithms for Sequential Modular Decomposition
Identifieur interne : 009874 ( Main/Merge ); précédent : 009873; suivant : 009875Efficient and Practical Algorithms for Sequential Modular Decomposition
Auteurs : Elias Dahlhaus [Allemagne] ; Jens Gustedt [France] ; Ross M. McconnellSource :
- Journal of Algorithms [ 0196-6774 ] ; 2001.
English descriptors
- 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
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
Links to Exploration step
ISTEX:2B312D136D8B44D49ED167F1E0FC86882A71AC7CLe 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></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="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></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></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 009874 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 009874 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:2B312D136D8B44D49ED167F1E0FC86882A71AC7C
|texte= Efficient and Practical Algorithms for Sequential Modular Decomposition
}}
| This area was generated with Dilib version V0.6.33. |  |