A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements
- Author
- CHU, Frank Pok Man1
[1] Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, ON, M5S 3G4, Canada - Source
Information processing letters. 2008, Vol 107, Num 1, pp 7-12, 6 p ; ref : 9 ref
- CODEN
- IFPLAT
- ISSN
- 0020-0190
- Scientific domain
- Computer science
- Publisher
- Elsevier Science, Amsterdam
- Publication country
- Netherlands
- Document type
- Article
- Language
- English
- Author keyword
- Algorithms Combinatorial problems Graph algorithms
- Keyword (fr)
- Addition Analyse algorithme Enquête Graphe linéaire Informatique théorique Partition Problème combinatoire Seuil Temps linéaire Traitement information 68R10 68Wxx Algorithme graphe Algorithme linéaire Algorithme temps linéaire Graphe parfait Recherche largeur d'abord Recherche largeur Reconnaissance graphe
- Keyword (en)
- Addition Algorithm analysis Survey Linear graph Computer theory Partition Combinatorial problem Threshold Linear time Information processing Graph algorithm
- Keyword (es)
- Adicción Análisis algoritmo Encuesta Grafo lineal Informática teórica Partición Problema combinatorio Umbral Tiempo lineal Procesamiento información
- Classification
- Pascal
- 001 Exact sciences and technology / 001D Applied sciences / 001D02 Computer science; control theory; systems / 001D02A Theoretical computing / 001D02A05 Algorithmics. Computability. Computer arithmetics
- Pascal
- 001 Exact sciences and technology / 001D Applied sciences / 001D02 Computer science; control theory; systems / 001D02A Theoretical computing / 001D02A06 Information retrieval. Graph
- Pascal
- 001 Exact sciences and technology / 001D Applied sciences / 001D02 Computer science; control theory; systems / 001D02A Theoretical computing / 001D02A08 Miscellaneous
- Discipline
- Computer science : theoretical automation and systems
- Origin
- Inist-CNRS
- Database
- PASCAL
- INIST identifier
- 20393199
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Access to the document
Install on your browser
DOI
10.1016/j.ipl.2007.12.009 
https://dx.doi.org/10.1016/j.ipl.2007.12.009
"O:13:\"PanistOpenUrl\":36:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000idc\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1016\/j.ipl.2007.12.009\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:9:\"\u0000*\u0000jtitle\";s:30:\"Information processing letters\";s:9:\"\u0000*\u0000stitle\";s:18:\"Inf. process. lett\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"107\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:1:\"7\";s:8:\"\u0000*\u0000epage\";s:2:\"12\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0020-0190\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:3:\"CHU\";s:10:\"\u0000*\u0000aufirst\";s:13:\"Frank Pok Man\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:0:{}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"IFPLAT\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:8:\"\u0000*\u0000place\";s:9:\"Amsterdam\";s:6:\"\u0000*\u0000pub\";s:16:\"Elsevier Science\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:1:\"6\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Panist access
"O:12:\"IstexOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1016\/j.ipl.2007.12.009\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:9:\"\u0000*\u0000jtitle\";s:30:\"Information processing letters\";s:9:\"\u0000*\u0000stitle\";s:18:\"Inf. process. lett\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"107\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:1:\"7\";s:8:\"\u0000*\u0000epage\";s:2:\"12\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0020-0190\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:3:\"CHU\";s:10:\"\u0000*\u0000aufirst\";s:13:\"Frank Pok Man\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:0:{}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"IFPLAT\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:8:\"\u0000*\u0000place\";s:9:\"Amsterdam\";s:6:\"\u0000*\u0000pub\";s:16:\"Elsevier Science\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:1:\"6\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Istex access
"O:16:\"UnpaywallOpenUrl\":35:{s:8:\"\u0000*\u0000email\";s:27:\"assistance-portail@inist.fr\";s:6:\"\u0000*\u0000fmt\";N;s:6:\"\u0000*\u0000doi\";s:25:\"10.1016\/j.ipl.2007.12.009\";s:6:\"\u0000*\u0000pii\";N;s:7:\"\u0000*\u0000pmid\";N;s:9:\"\u0000*\u0000atitle\";N;s:9:\"\u0000*\u0000jtitle\";N;s:9:\"\u0000*\u0000stitle\";N;s:7:\"\u0000*\u0000date\";N;s:9:\"\u0000*\u0000volume\";N;s:8:\"\u0000*\u0000issue\";N;s:8:\"\u0000*\u0000spage\";N;s:8:\"\u0000*\u0000epage\";N;s:8:\"\u0000*\u0000pages\";N;s:7:\"\u0000*\u0000issn\";N;s:8:\"\u0000*\u0000eissn\";N;s:9:\"\u0000*\u0000aulast\";N;s:10:\"\u0000*\u0000aufirst\";N;s:9:\"\u0000*\u0000auinit\";N;s:10:\"\u0000*\u0000auinitm\";N;s:5:\"\u0000*\u0000au\";N;s:9:\"\u0000*\u0000aucorp\";N;s:7:\"\u0000*\u0000isbn\";N;s:8:\"\u0000*\u0000coden\";N;s:8:\"\u0000*\u0000genre\";N;s:7:\"\u0000*\u0000part\";N;s:9:\"\u0000*\u0000btitle\";N;s:8:\"\u0000*\u0000title\";N;s:8:\"\u0000*\u0000place\";N;s:6:\"\u0000*\u0000pub\";N;s:10:\"\u0000*\u0000edition\";N;s:9:\"\u0000*\u0000tpages\";N;s:9:\"\u0000*\u0000series\";N;s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";N;}"
Unpaywall access
"O:16:\"EuropePMCOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1016\/j.ipl.2007.12.009\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:9:\"\u0000*\u0000jtitle\";s:30:\"Information processing letters\";s:9:\"\u0000*\u0000stitle\";s:18:\"Inf. process. lett\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"107\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:1:\"7\";s:8:\"\u0000*\u0000epage\";s:2:\"12\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0020-0190\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:3:\"CHU\";s:10:\"\u0000*\u0000aufirst\";s:13:\"Frank Pok Man\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:0:{}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"IFPLAT\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:8:\"\u0000*\u0000place\";s:9:\"Amsterdam\";s:6:\"\u0000*\u0000pub\";s:16:\"Elsevier Science\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:1:\"6\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Europe PubMed Central access
"O:11:\"BaseOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1016\/j.ipl.2007.12.009\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:9:\"\u0000*\u0000jtitle\";s:30:\"Information processing letters\";s:9:\"\u0000*\u0000stitle\";s:18:\"Inf. process. lett\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"107\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:1:\"7\";s:8:\"\u0000*\u0000epage\";s:2:\"12\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0020-0190\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:3:\"CHU\";s:10:\"\u0000*\u0000aufirst\";s:13:\"Frank Pok Man\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:0:{}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"IFPLAT\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:8:\"\u0000*\u0000place\";s:9:\"Amsterdam\";s:6:\"\u0000*\u0000pub\";s:16:\"Elsevier Science\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:1:\"6\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
Base Search access
"O:12:\"ArXivOpenUrl\":35:{s:10:\"\u0000*\u0000openUrl\";N;s:6:\"\u0000*\u0000fmt\";s:7:\"journal\";s:6:\"\u0000*\u0000doi\";s:25:\"10.1016\/j.ipl.2007.12.009\";s:6:\"\u0000*\u0000pii\";s:0:\"\";s:7:\"\u0000*\u0000pmid\";s:0:\"\";s:9:\"\u0000*\u0000atitle\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:9:\"\u0000*\u0000jtitle\";s:30:\"Information processing letters\";s:9:\"\u0000*\u0000stitle\";s:18:\"Inf. process. lett\";s:7:\"\u0000*\u0000date\";s:4:\"2008\";s:9:\"\u0000*\u0000volume\";s:3:\"107\";s:8:\"\u0000*\u0000issue\";s:1:\"1\";s:8:\"\u0000*\u0000spage\";s:1:\"7\";s:8:\"\u0000*\u0000epage\";s:2:\"12\";s:8:\"\u0000*\u0000pages\";s:0:\"\";s:7:\"\u0000*\u0000issn\";s:9:\"0020-0190\";s:8:\"\u0000*\u0000eissn\";s:0:\"\";s:9:\"\u0000*\u0000aulast\";s:3:\"CHU\";s:10:\"\u0000*\u0000aufirst\";s:13:\"Frank Pok Man\";s:9:\"\u0000*\u0000auinit\";s:0:\"\";s:10:\"\u0000*\u0000auinitm\";s:0:\"\";s:5:\"\u0000*\u0000au\";a:0:{}s:9:\"\u0000*\u0000aucorp\";s:0:\"\";s:7:\"\u0000*\u0000isbn\";s:0:\"\";s:8:\"\u0000*\u0000coden\";s:6:\"IFPLAT\";s:8:\"\u0000*\u0000genre\";s:7:\"article\";s:7:\"\u0000*\u0000part\";s:0:\"\";s:9:\"\u0000*\u0000btitle\";s:0:\"\";s:8:\"\u0000*\u0000title\";s:115:\"A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements\";s:8:\"\u0000*\u0000place\";s:9:\"Amsterdam\";s:6:\"\u0000*\u0000pub\";s:16:\"Elsevier Science\";s:10:\"\u0000*\u0000edition\";s:0:\"\";s:9:\"\u0000*\u0000tpages\";s:1:\"6\";s:9:\"\u0000*\u0000series\";s:0:\"\";s:8:\"\u0000*\u0000proxy\";s:30:\"http:\/\/proxyout.inist.fr:8080\/\";s:12:\"\u0000*\u0000integrite\";b:1;}"
arXiv access
