InforLorV4, Main, Merge, bibRecord, 009989

Efficient and practical algorithms for sequential modular decomposition

Identifieur interne : 009989 ( Main/Merge ); précédent : 009988; suivant : 009990

Efficient and practical algorithms for sequential modular decomposition

Auteurs : Elias Dahlhaus [Allemagne] ; Jens Gustedt [France] ; Ross M. Mcconnell [États-Unis]

Source :

Journal of algorithms : (Print) [ 0196-6774 ] ; 2001.

RBID : Pascal:02-0139077

Descripteurs français

Pascal (Inist)
- Théorie graphe, Décomposition graphe, Construction modulaire, Algorithme, Extraction séquentielle, Efficacité, Congruence, Sous graphe, Partition, Complexité temps, Borne inférieure, Borne supérieure, Décomposition séquentielle.

English descriptors

KwdEn :
- Algorithm, Congruence, Efficiency, Graph decomposition, Graph theory, Lower bound, Modular construction, Partition, Sequential decomposition, Sequential extraction, Subgraph, Time complexity, Upper bound.

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 + ma(m, n)) time bound and a variant with a linear time bound.

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000889
to stream PascalFrancis, to step Curation: 000163
to stream PascalFrancis, to step Checkpoint: 000906

Links to Exploration step

Pascal:02-0139077

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">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"><inist:fA14 i1="01"><s1>Department of Computer Science and Department of Mathematics, University of Cologne</s1>
<s2>Cologne</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>Cologne</wicri:noRegion>
<wicri:noRegion>University of 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"><inist:fA14 i1="02"><s1>LORIA and INRIA Lorraine, campus scientifique, BP 239</s1>
<s2>54506, Vandœuvre lés Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
<settlement type="city" wicri:auto="agglo">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:level="1"><inist:fA14 i1="03"><s1>Department of Computer Science and Engineering University of Colorado at Denver</s1>
<s2>Denver, Colorado 80217-3364</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Department of Computer Science and Engineering University of Colorado at Denver</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">02-0139077</idno>
<date when="2001">2001</date>
<idno type="stanalyst">PASCAL 02-0139077 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>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">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"><inist:fA14 i1="01"><s1>Department of Computer Science and Department of Mathematics, University of Cologne</s1>
<s2>Cologne</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
<country>Allemagne</country>
<wicri:noRegion>Cologne</wicri:noRegion>
<wicri:noRegion>University of 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"><inist:fA14 i1="02"><s1>LORIA and INRIA Lorraine, campus scientifique, BP 239</s1>
<s2>54506, Vandœuvre lés Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
<country>France</country>
<placeName><region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandœuvre-lès-Nancy</settlement>
<settlement type="city" wicri:auto="agglo">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:level="1"><inist:fA14 i1="03"><s1>Department of Computer Science and Engineering University of Colorado at Denver</s1>
<s2>Denver, Colorado 80217-3364</s2>
<s3>USA</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
<country>États-Unis</country>
<wicri:noRegion>Department of Computer Science and Engineering University of Colorado at Denver</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Journal of algorithms : (Print)</title>
<title level="j" type="abbreviated">J. algorithms : (Print)</title>
<idno type="ISSN">0196-6774</idno>
<imprint><date when="2001">2001</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Journal of algorithms : (Print)</title>
<title level="j" type="abbreviated">J. algorithms : (Print)</title>
<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>Théorie graphe</term>
<term>Décomposition graphe</term>
<term>Construction modulaire</term>
<term>Algorithme</term>
<term>Extraction séquentielle</term>
<term>Efficacité</term>
<term>Congruence</term>
<term>Sous graphe</term>
<term>Partition</term>
<term>Complexité temps</term>
<term>Borne inférieure</term>
<term>Borne supérieure</term>
<term>Décomposition séquentielle</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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 + ma(m, n)) time bound and a variant with a linear time bound.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
<li>États-Unis</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Nancy</li>
<li>Vandœuvre-lès-Nancy</li>
</settlement>
</list>
<tree><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>
<country name="États-Unis"><noRegion><name sortKey="Mcconnell, Ross M" sort="Mcconnell, Ross M" uniqKey="Mcconnell R" first="Ross M." last="Mcconnell">Ross M. Mcconnell</name>
</noRegion>
</country>
</tree>
</affiliations>
</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 009989 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 009989 | 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é=     Pascal:02-0139077
   |texte=   Efficient and practical algorithms for sequential modular decomposition
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Efficient and practical algorithms for sequential modular decomposition

Efficient and practical algorithms for sequential modular decomposition

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri