CIRM - Videos & books LibraryDocuments

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science

Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings.
These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance) on some special classes of graphs such as cocomparability graphs.
In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids. These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate. Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such ...

Documents

Thesaurus

Revues

Documents 68R10 | enregistrements trouvés : 105

New perspectives for graph searches on structured families of graphs Habib, Michel | CIRM H Nouveau

Le problème Graph Motif - Partie 1 Fertin, Guillaume | CIRM H Nouveau

Combinatorial optimization,annotated bibliographiessummer school on combinatorial optimization held in dublin,july 4-15,1983 Lenstra, J. K. ; O'Heigeartaigh, M. ; Rinnooy Kan, A. H. G. | John Wiley And Sons 1985 Nouveau

Discrete algorithms and complexity :proceedings of the Japan-u.s. joint seminar#June 4-6 Johnson, D. S. ; Nishizeki, T. ; Nozaki, A. ; Wilf, H. S. | Academic Press Inc. 1987 Nouveau

26th annual symposium on foundations of computer sciencesymposium on... held on oct. 21-23,1985,in portland,oregon | Ieee Computer Society Press 1985 Nouveau

Graph theory with applications to algorithms and computer sciencefifth quadrennial international conference on... held at western michigan univ.,in kalamazoo,michigan,june 4-8, 1984 Alavi, Y. ; Chartrand, G. ; Lesniak, L. | John Wiley And Sons 1985 Nouveau

Graphtheoretic concepts in computer science :proceedings of the international workshop wg 80 was held at bad honnef#June 15-17 Noltemeier, Hartmut | Springer-Verlag 1981 Nouveau

Caap '86 :11th colloquium on trees in algebra and programming#March 24-26 Franchi-Zannettacci, P. | Springer-Verlag 1986 Nouveau

Automata, languages and programming :13th international colloquium#July 15-19 Kott, Laurent | Springer-Verlag 1986 Nouveau

Combinatorics and theoretical computer scienceproceedings of the capital city conference on... Simion, R. | North-Holland 1992 Nouveau

Automata, languages, and programming :19th international colloquium#July 13-17 Kuich, W. | Springer-Verlag 1992 Nouveau

Combinatorics'90recent trends and applicationsproceedings of the conference on combinatoricsmay 20-27 Barlotti, A. ; Bichara, A. ; Ceccherini, P. V. ; Tallini, G. | North-Holland 1992 Nouveau

Foundations of software technology and theorical computer science#Dec. 18-20 Shyamasundar, R. | Springer-Verlag 1992 Nouveau

Graph-theoretic concepts in computer science :18 th international workshop WG'92#June 18-20 Mayr, E. W. | Springer-Verlag 1993 Nouveau

Trees in algebra and programming-CAAP '94 :19th international colloquium trees in algebra and programming-CAAP '94#April 11-13 Tison, Sophie | Springer-Verlag 1994 Nouveau

Advances in computational complexity theory :selected collection of refereed papers representing the DIMACS special year and most particularly the workshop on structural complexity and cryptography#Dec. 3-7 Cai, Jin-Yi | American Mathematical Society 1993 Nouveau

Graph drawing :symposium on...GD'95#Sept. 20-22 Brandenburg, Franz J. | Springer 1996 Nouveau

LATIN'95 :theoretical informatics#seconde latin american symposium#April 3-7 Baeza-Yates Ricardo ; Goles, Eric ; Poblete, Patricio V. | Springer 1995 Nouveau

Graph drawing :DIMACS international workshop, GD'94#Oct. 10-12 Tamassia, Roberto ; Tollis, Ioannis G. | Springer 1995 Nouveau

Cliques, coloring, and satisfiability :second DIMACS implementation challenge Rutgers University and Princeton University#Oct. 11-13 Johnson, David S. ; Trick, Michael A. | American Mathematical Society 1996 Nouveau

Filtrer

Type

Domaine

Codes MSC

Documents

Références

Auteurs

Thesaurus

Combinatorial optimization,annotated bibliographies
summer school on combinatorial optimization held in dublin,july 4-15,1983 Lenstra, J. K. ; O'Heigeartaigh, M. ; Rinnooy Kan, A. H. G. | John Wiley And Sons 1985 Nouveau

Discrete algorithms and complexity :
proceedings of the Japan-u.s. joint seminar#June 4-6 Johnson, D. S. ; Nishizeki, T. ; Nozaki, A. ; Wilf, H. S. | Academic Press Inc. 1987 Nouveau

26th annual symposium on foundations of computer science
symposium on... held on oct. 21-23,1985,in portland,oregon | Ieee Computer Society Press 1985 Nouveau

Graph theory with applications to algorithms and computer science
fifth quadrennial international conference on... held at western michigan univ.,in kalamazoo,michigan,june 4-8, 1984 Alavi, Y. ; Chartrand, G. ; Lesniak, L. | John Wiley And Sons 1985 Nouveau

Graphtheoretic concepts in computer science :
proceedings of the international workshop wg 80 was held at bad honnef#June 15-17 Noltemeier, Hartmut | Springer-Verlag 1981 Nouveau

Caap '86 :
11th colloquium on trees in algebra and programming#March 24-26 Franchi-Zannettacci, P. | Springer-Verlag 1986 Nouveau

Automata, languages and programming :
13th international colloquium#July 15-19 Kott, Laurent | Springer-Verlag 1986 Nouveau

Combinatorics and theoretical computer science
proceedings of the capital city conference on... Simion, R. | North-Holland 1992 Nouveau

Automata, languages, and programming :
19th international colloquium#July 13-17 Kuich, W. | Springer-Verlag 1992 Nouveau

Combinatorics'90
recent trends and applications
proceedings of the conference on combinatorics
may 20-27 Barlotti, A. ; Bichara, A. ; Ceccherini, P. V. ; Tallini, G. | North-Holland 1992 Nouveau

Graph-theoretic concepts in computer science :
18 th international workshop WG'92#June 18-20 Mayr, E. W. | Springer-Verlag 1993 Nouveau

Trees in algebra and programming-CAAP '94 :
19th international colloquium trees in algebra and programming-CAAP '94#April 11-13 Tison, Sophie | Springer-Verlag 1994 Nouveau

Advances in computational complexity theory :
selected collection of refereed papers representing the DIMACS special year and most particularly the workshop on structural complexity and cryptography#Dec. 3-7 Cai, Jin-Yi | American Mathematical Society 1993 Nouveau

Graph drawing :
symposium on...GD'95#Sept. 20-22 Brandenburg, Franz J. | Springer 1996 Nouveau

LATIN'95 :
theoretical informatics#seconde latin american symposium#April 3-7 Baeza-Yates Ricardo ; Goles, Eric ; Poblete, Patricio V. | Springer 1995 Nouveau

Graph drawing :
DIMACS international workshop, GD'94#Oct. 10-12 Tamassia, Roberto ; Tollis, Ioannis G. | Springer 1995 Nouveau

Cliques, coloring, and satisfiability :
second DIMACS implementation challenge Rutgers University and Princeton University#Oct. 11-13 Johnson, David S. ; Trick, Michael A. | American Mathematical Society 1996 Nouveau