InforLorV4, PascalFrancis, Corpus, bibRecord, 000584

The perfection and recognition of bull-reducible Berge graphs

Identifieur interne : 000584 ( PascalFrancis/Corpus ); précédent : 000583; suivant : 000585

The perfection and recognition of bull-reducible Berge graphs

Auteurs : Hazel Everett ; Celina M. H. De Figueiredo ; Sulamita Klein ; Bruce Reed

Source :

Informatique théorique et applications : (Imprimé) [ 0988-3754 ] ; 2005.

RBID : Pascal:05-0168932

Descripteurs français

Pascal (Inist)
- Reconnaissance, Cycle graphe, Classe complexité, Informatique théorique, Graphe Berge, 68R10, Graphe parfait, Algorithme reconnaissance, 68Wxx.

English descriptors

KwdEn :
- Complexity class, Computer theory, Cycle(graph), Recognition.

Abstract

The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n⁶), is much lower than that announced for perfect graphs.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0988-3754`
A02	`01`			`@0 RITAE4`
A03		`1`		`@0 Inform. théor. appl. : (Imprimé`
A05				`@2 39`
A06				`@2 1`
A08	`01`	`1`	`ENG`	`@1 The perfection and recognition of bull-reducible Berge graphs`
A11	`01`	`1`		`@1 EVERETT (Hazel)`
A11	`02`	`1`		`@1 DE FIGUEIREDO (Celina M. H.)`
A11	`03`	`1`		`@1 KLEIN (Sulamita)`
A11	`04`	`1`		`@1 REED (Bruce)`
A14	`01`			`@1 LORIA @3 FRA @Z 1 aut.`
A14	`02`			`@1 Universidade Federal do Rio de Janeiro @2 Brasil @3 BRA @Z 2 aut. @Z 3 aut.`
A14	`03`			`@1 McGill University @3 CAN @Z 4 aut.`
A20				`@1 145-160`
A21				`@1 2005`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 9323B2 @5 354000126438630090`
A44				`@0 0000 @1 © 2005 INIST-CNRS. All rights reserved.`
A45				`@0 16 ref.`
A47	`01`	`1`		`@0 05-0168932`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Informatique théorique et applications : (Imprimé)`
A66	`01`			`@0 FRA`
C01	`01`		`ENG`	@0 The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n⁶), is much lower than that announced for perfect graphs.
C02	`01`	`X`		`@0 001A02B01C`
C03	`01`	`X`	`FRE`	`@0 Reconnaissance @5 17`
C03	`01`	`X`	`ENG`	`@0 Recognition @5 17`
C03	`01`	`X`	`SPA`	`@0 Reconocimiento @5 17`
C03	`02`	`X`	`FRE`	`@0 Cycle graphe @5 18`
C03	`02`	`X`	`ENG`	`@0 Cycle(graph) @5 18`
C03	`02`	`X`	`SPA`	`@0 Ciclo diagrama @5 18`
C03	`03`	`X`	`FRE`	`@0 Classe complexité @5 20`
C03	`03`	`X`	`ENG`	`@0 Complexity class @5 20`
C03	`03`	`X`	`SPA`	`@0 Clase complejidad @5 20`
C03	`04`	`X`	`FRE`	`@0 Informatique théorique @5 22`
C03	`04`	`X`	`ENG`	`@0 Computer theory @5 22`
C03	`04`	`X`	`SPA`	`@0 Informática teórica @5 22`
C03	`05`	`X`	`FRE`	`@0 Graphe Berge @4 INC @5 70`
C03	`06`	`X`	`FRE`	`@0 68R10 @4 INC @5 71`
C03	`07`	`X`	`FRE`	`@0 Graphe parfait @4 INC @5 72`
C03	`08`	`X`	`FRE`	`@0 Algorithme reconnaissance @4 INC @5 73`
C03	`09`	`X`	`FRE`	`@0 68Wxx @4 INC @5 74`
N21				`@1 115`
N44	`01`			`@1 OTO`
N82				`@1 OTO`

Format Inist (serveur)

NO :	PASCAL 05-0168932 INIST
ET :	The perfection and recognition of bull-reducible Berge graphs
AU :	EVERETT (Hazel); DE FIGUEIREDO (Celina M. H.); KLEIN (Sulamita); REED (Bruce)
AF :	LORIA/France (1 aut.); Universidade Federal do Rio de Janeiro/Brasil/Brésil (2 aut., 3 aut.); McGill University/Canada (4 aut.)
DT :	Publication en série; Niveau analytique
SO :	Informatique théorique et applications : (Imprimé); ISSN 0988-3754; Coden RITAE4; France; Da. 2005; Vol. 39; No. 1; Pp. 145-160; Bibl. 16 ref.
LA :	Anglais
EA :	The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n⁶), is much lower than that announced for perfect graphs.
CC :	001A02B01C
FD :	Reconnaissance; Cycle graphe; Classe complexité; Informatique théorique; Graphe Berge; 68R10; Graphe parfait; Algorithme reconnaissance; 68Wxx
ED :	Recognition; Cycle(graph); Complexity class; Computer theory
SD :	Reconocimiento; Ciclo diagrama; Clase complejidad; Informática teórica
LO :	INIST-9323B2.354000126438630090
ID :	05-0168932

Links to Exploration step

Pascal:05-0168932

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">The perfection and recognition of bull-reducible Berge graphs</title>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="De Figueiredo, Celina M H" sort="De Figueiredo, Celina M H" uniqKey="De Figueiredo C" first="Celina M. H." last="De Figueiredo">Celina M. H. De Figueiredo</name>
<affiliation><inist:fA14 i1="02"><s1>Universidade Federal do Rio de Janeiro</s1>
<s2>Brasil</s2>
<s3>BRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Klein, Sulamita" sort="Klein, Sulamita" uniqKey="Klein S" first="Sulamita" last="Klein">Sulamita Klein</name>
<affiliation><inist:fA14 i1="02"><s1>Universidade Federal do Rio de Janeiro</s1>
<s2>Brasil</s2>
<s3>BRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Reed, Bruce" sort="Reed, Bruce" uniqKey="Reed B" first="Bruce" last="Reed">Bruce Reed</name>
<affiliation><inist:fA14 i1="03"><s1>McGill University</s1>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">05-0168932</idno>
<date when="2005">2005</date>
<idno type="stanalyst">PASCAL 05-0168932 INIST</idno>
<idno type="RBID">Pascal:05-0168932</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000584</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">The perfection and recognition of bull-reducible Berge graphs</title>
<author><name sortKey="Everett, Hazel" sort="Everett, Hazel" uniqKey="Everett H" first="Hazel" last="Everett">Hazel Everett</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="De Figueiredo, Celina M H" sort="De Figueiredo, Celina M H" uniqKey="De Figueiredo C" first="Celina M. H." last="De Figueiredo">Celina M. H. De Figueiredo</name>
<affiliation><inist:fA14 i1="02"><s1>Universidade Federal do Rio de Janeiro</s1>
<s2>Brasil</s2>
<s3>BRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Klein, Sulamita" sort="Klein, Sulamita" uniqKey="Klein S" first="Sulamita" last="Klein">Sulamita Klein</name>
<affiliation><inist:fA14 i1="02"><s1>Universidade Federal do Rio de Janeiro</s1>
<s2>Brasil</s2>
<s3>BRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Reed, Bruce" sort="Reed, Bruce" uniqKey="Reed B" first="Bruce" last="Reed">Bruce Reed</name>
<affiliation><inist:fA14 i1="03"><s1>McGill University</s1>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">Informatique théorique et applications : (Imprimé)</title>
<title level="j" type="abbreviated">Inform. théor. appl. : (Imprimé</title>
<idno type="ISSN">0988-3754</idno>
<imprint><date when="2005">2005</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Informatique théorique et applications : (Imprimé)</title>
<title level="j" type="abbreviated">Inform. théor. appl. : (Imprimé</title>
<idno type="ISSN">0988-3754</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Complexity class</term>
<term>Computer theory</term>
<term>Cycle(graph)</term>
<term>Recognition</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Reconnaissance</term>
<term>Cycle graphe</term>
<term>Classe complexité</term>
<term>Informatique théorique</term>
<term>Graphe Berge</term>
<term>68R10</term>
<term>Graphe parfait</term>
<term>Algorithme reconnaissance</term>
<term>68Wxx</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n<sup>6</sup>
), is much lower than that announced for perfect graphs.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0988-3754</s0>
</fA01>
<fA02 i1="01"><s0>RITAE4</s0>
</fA02>
<fA03 i2="1"><s0>Inform. théor. appl. : (Imprimé</s0>
</fA03>
<fA05><s2>39</s2>
</fA05>
<fA06><s2>1</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>The perfection and recognition of bull-reducible Berge graphs</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>EVERETT (Hazel)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>DE FIGUEIREDO (Celina M. H.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>KLEIN (Sulamita)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>REED (Bruce)</s1>
</fA11>
<fA14 i1="01"><s1>LORIA</s1>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>Universidade Federal do Rio de Janeiro</s1>
<s2>Brasil</s2>
<s3>BRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
</fA14>
<fA14 i1="03"><s1>McGill University</s1>
<s3>CAN</s3>
<sZ>4 aut.</sZ>
</fA14>
<fA20><s1>145-160</s1>
</fA20>
<fA21><s1>2005</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>9323B2</s2>
<s5>354000126438630090</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2005 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>16 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>05-0168932</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Informatique théorique et applications : (Imprimé)</s0>
</fA64>
<fA66 i1="01"><s0>FRA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n<sup>6</sup>
), is much lower than that announced for perfect graphs.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001A02B01C</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Reconnaissance</s0>
<s5>17</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Recognition</s0>
<s5>17</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Reconocimiento</s0>
<s5>17</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Cycle graphe</s0>
<s5>18</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Cycle(graph)</s0>
<s5>18</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Ciclo diagrama</s0>
<s5>18</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Classe complexité</s0>
<s5>20</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Complexity class</s0>
<s5>20</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Clase complejidad</s0>
<s5>20</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>22</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>22</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>22</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Graphe Berge</s0>
<s4>INC</s4>
<s5>70</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>68R10</s0>
<s4>INC</s4>
<s5>71</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Graphe parfait</s0>
<s4>INC</s4>
<s5>72</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Algorithme reconnaissance</s0>
<s4>INC</s4>
<s5>73</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>68Wxx</s0>
<s4>INC</s4>
<s5>74</s5>
</fC03>
<fN21><s1>115</s1>
</fN21>
<fN44 i1="01"><s1>OTO</s1>
</fN44>
<fN82><s1>OTO</s1>
</fN82>
</pA>
</standard>
<server><NO>PASCAL 05-0168932 INIST</NO>
<ET>The perfection and recognition of bull-reducible Berge graphs</ET>
<AU>EVERETT (Hazel); DE FIGUEIREDO (Celina M. H.); KLEIN (Sulamita); REED (Bruce)</AU>
<AF>LORIA/France (1 aut.); Universidade Federal do Rio de Janeiro/Brasil/Brésil (2 aut., 3 aut.); McGill University/Canada (4 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Informatique théorique et applications : (Imprimé); ISSN 0988-3754; Coden RITAE4; France; Da. 2005; Vol. 39; No. 1; Pp. 145-160; Bibl. 16 ref.</SO>
<LA>Anglais</LA>
<EA>The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices x, a, b, c, d and five edges xa, xb, ab, ad, bc. A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n<sup>6</sup>
), is much lower than that announced for perfect graphs.</EA>
<CC>001A02B01C</CC>
<FD>Reconnaissance; Cycle graphe; Classe complexité; Informatique théorique; Graphe Berge; 68R10; Graphe parfait; Algorithme reconnaissance; 68Wxx</FD>
<ED>Recognition; Cycle(graph); Complexity class; Computer theory</ED>
<SD>Reconocimiento; Ciclo diagrama; Clase complejidad; Informática teórica</SD>
<LO>INIST-9323B2.354000126438630090</LO>
<ID>05-0168932</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

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

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

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000584 | SxmlIndent | more

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

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:05-0168932
   |texte=   The perfection and recognition of bull-reducible Berge graphs
}}

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

The perfection and recognition of bull-reducible Berge graphs

The perfection and recognition of bull-reducible Berge graphs

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

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