Curation
PascalFrancis
Racine
Curation
Checkpoint
PascalFrancis
Racine
PascalFrancis
Exploration
Accueil
Racine
Racine

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.

Efficient and practical algorithms for sequential modular decomposition

Identifieur interne : 000163 ( PascalFrancis/Curation ); précédent : 000162; suivant : 000164

Efficient and practical algorithms for sequential modular decomposition

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

Source :

RBID : Pascal:02-0139077

Descripteurs français

English descriptors

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.
pA  
A01 01  1    @0 0196-6774
A02 01      @0 JOALDV
A03   1    @0 J. algorithms : (Print)
A05       @2 41
A06       @2 2
A08 01  1  ENG  @1 Efficient and practical algorithms for sequential modular decomposition
A11 01  1    @1 DAHLHAUS (Elias)
A11 02  1    @1 GUSTEDT (Jens)
A11 03  1    @1 MCCONNELL (Ross M.)
A14 01      @1 Department of Computer Science and Department of Mathematics, University of Cologne @2 Cologne @3 DEU @Z 1 aut.
A14 02      @1 LORIA and INRIA Lorraine, campus scientifique, BP 239 @2 54506, Vandœuvre lés Nancy @3 FRA @Z 2 aut.
A14 03      @1 Department of Computer Science and Engineering University of Colorado at Denver @2 Denver, Colorado 80217-3364 @3 USA @Z 3 aut.
A20       @1 360-387
A21       @1 2001
A23 01      @0 ENG
A43 01      @1 INIST @2 18373 @5 354000094692230110
A44       @0 0000 @1 © 2002 INIST-CNRS. All rights reserved.
A45       @0 28 ref.
A47 01  1    @0 02-0139077
A60       @1 P
A61       @0 A
A64 01  1    @0 Journal of algorithms : (Print)
A66 01      @0 USA
C01 01    ENG  @0 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.
C02 01  X    @0 001A02B01C
C03 01  X  FRE  @0 Théorie graphe @5 01
C03 01  X  ENG  @0 Graph theory @5 01
C03 01  X  SPA  @0 Teoría grafo @5 01
C03 02  X  FRE  @0 Décomposition graphe @5 02
C03 02  X  ENG  @0 Graph decomposition @5 02
C03 02  X  SPA  @0 Descomposición grafo @5 02
C03 03  X  FRE  @0 Construction modulaire @5 03
C03 03  X  ENG  @0 Modular construction @5 03
C03 03  X  SPA  @0 Construcción modular @5 03
C03 04  X  FRE  @0 Algorithme @5 04
C03 04  X  ENG  @0 Algorithm @5 04
C03 04  X  SPA  @0 Algoritmo @5 04
C03 05  X  FRE  @0 Extraction séquentielle @5 05
C03 05  X  ENG  @0 Sequential extraction @5 05
C03 05  X  SPA  @0 Extracción secuenciala @5 05
C03 06  X  FRE  @0 Efficacité @5 06
C03 06  X  ENG  @0 Efficiency @5 06
C03 06  X  SPA  @0 Eficacia @5 06
C03 07  X  FRE  @0 Congruence @5 07
C03 07  X  ENG  @0 Congruence @5 07
C03 07  X  SPA  @0 Congruencia @5 07
C03 08  X  FRE  @0 Sous graphe @5 08
C03 08  X  ENG  @0 Subgraph @5 08
C03 08  X  SPA  @0 Subgrafo @5 08
C03 09  X  FRE  @0 Partition @5 09
C03 09  X  ENG  @0 Partition @5 09
C03 09  X  SPA  @0 Partición @5 09
C03 10  X  FRE  @0 Complexité temps @5 10
C03 10  X  ENG  @0 Time complexity @5 10
C03 10  X  SPA  @0 Complejidad tiempo @5 10
C03 11  X  FRE  @0 Borne inférieure @5 11
C03 11  X  ENG  @0 Lower bound @5 11
C03 11  X  SPA  @0 Cota inferior @5 11
C03 12  X  FRE  @0 Borne supérieure @5 12
C03 12  X  ENG  @0 Upper bound @5 12
C03 12  X  SPA  @0 Cota superior @5 12
C03 13  X  FRE  @0 Décomposition séquentielle @4 CD @5 96
C03 13  X  ENG  @0 Sequential decomposition @4 CD @5 96
N21       @1 077

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

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>
</affiliation>
</author>
<author>
<name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name>
<affiliation wicri:level="1">
<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>
</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>
</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>
</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>
</affiliation>
</author>
<author>
<name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name>
<affiliation wicri:level="1">
<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>
</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>
</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>
<inist>
<standard h6="B">
<pA>
<fA01 i1="01" i2="1">
<s0>0196-6774</s0>
</fA01>
<fA02 i1="01">
<s0>JOALDV</s0>
</fA02>
<fA03 i2="1">
<s0>J. algorithms : (Print)</s0>
</fA03>
<fA05>
<s2>41</s2>
</fA05>
<fA06>
<s2>2</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG">
<s1>Efficient and practical algorithms for sequential modular decomposition</s1>
</fA08>
<fA11 i1="01" i2="1">
<s1>DAHLHAUS (Elias)</s1>
</fA11>
<fA11 i1="02" i2="1">
<s1>GUSTEDT (Jens)</s1>
</fA11>
<fA11 i1="03" i2="1">
<s1>MCCONNELL (Ross M.)</s1>
</fA11>
<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>
</fA14>
<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>
</fA14>
<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>
</fA14>
<fA20>
<s1>360-387</s1>
</fA20>
<fA21>
<s1>2001</s1>
</fA21>
<fA23 i1="01">
<s0>ENG</s0>
</fA23>
<fA43 i1="01">
<s1>INIST</s1>
<s2>18373</s2>
<s5>354000094692230110</s5>
</fA43>
<fA44>
<s0>0000</s0>
<s1>© 2002 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45>
<s0>28 ref.</s0>
</fA45>
<fA47 i1="01" i2="1">
<s0>02-0139077</s0>
</fA47>
<fA60>
<s1>P</s1>
</fA60>
<fA61>
<s0>A</s0>
</fA61>
<fA64 i1="01" i2="1">
<s0>Journal of algorithms : (Print)</s0>
</fA64>
<fA66 i1="01">
<s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG">
<s0>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.</s0>
</fC01>
<fC02 i1="01" i2="X">
<s0>001A02B01C</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE">
<s0>Théorie graphe</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG">
<s0>Graph theory</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA">
<s0>Teoría grafo</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE">
<s0>Décomposition graphe</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG">
<s0>Graph decomposition</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA">
<s0>Descomposición grafo</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE">
<s0>Construction modulaire</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG">
<s0>Modular construction</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA">
<s0>Construcción modular</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE">
<s0>Algorithme</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG">
<s0>Algorithm</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA">
<s0>Algoritmo</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE">
<s0>Extraction séquentielle</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG">
<s0>Sequential extraction</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA">
<s0>Extracción secuenciala</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE">
<s0>Efficacité</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG">
<s0>Efficiency</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA">
<s0>Eficacia</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE">
<s0>Congruence</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG">
<s0>Congruence</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA">
<s0>Congruencia</s0>
<s5>07</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE">
<s0>Sous graphe</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG">
<s0>Subgraph</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA">
<s0>Subgrafo</s0>
<s5>08</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE">
<s0>Partition</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG">
<s0>Partition</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA">
<s0>Partición</s0>
<s5>09</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE">
<s0>Complexité temps</s0>
<s5>10</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG">
<s0>Time complexity</s0>
<s5>10</s5>
</fC03>
<fC03 i1="10" i2="X" l="SPA">
<s0>Complejidad tiempo</s0>
<s5>10</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE">
<s0>Borne inférieure</s0>
<s5>11</s5>
</fC03>
<fC03 i1="11" i2="X" l="ENG">
<s0>Lower bound</s0>
<s5>11</s5>
</fC03>
<fC03 i1="11" i2="X" l="SPA">
<s0>Cota inferior</s0>
<s5>11</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE">
<s0>Borne supérieure</s0>
<s5>12</s5>
</fC03>
<fC03 i1="12" i2="X" l="ENG">
<s0>Upper bound</s0>
<s5>12</s5>
</fC03>
<fC03 i1="12" i2="X" l="SPA">
<s0>Cota superior</s0>
<s5>12</s5>
</fC03>
<fC03 i1="13" i2="X" l="FRE">
<s0>Décomposition séquentielle</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="13" i2="X" l="ENG">
<s0>Sequential decomposition</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21>
<s1>077</s1>
</fN21>
</pA>
</standard>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000163 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000163 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Curation
   |type=    RBID
   |clé=     Pascal:02-0139077
   |texte=   Efficient and practical algorithms for sequential modular decomposition
}}
Wicri

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