F Nous contacter


0

Search by event  1660 | enregistrements trouvés : 5

O
     

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

The partially disjoint paths problem asks for paths $P_1, \ldots,P_k$ between given pairs of terminals, while certain pairs of paths $P_i$,$P_j$ are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed $k$, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems. No specific foreknowledge is required.

05C10 ; 05C20 ; 05C25 ; 05C38 ; 68Q25 ; 90C27

Multi angle  Restricted types of matchings
Rautenbach, Dieter (Auteur de la Conférence) | CIRM (Editeur )

We present new results concerning restricted types of matchings such as uniquely restricted matchings and acyclic matchings, and we also consider the corresponding edge coloring notions. Our focus lies on bounds, exact and approximative algorithms. Furthermore, we discuss some matching removal problems. The talk is based on joined work with J. Baste, C. Lima, L. Penso, I. Sau, U. Souza, and J. Szwarcfiter.

05C70 ; 05C35 ; 05C15 ; 05C85 ; 68Q25

Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit interval graphs, which are precisely the graphs having a Robinsonian adjacency matrix. We will discuss several aspects of Robinsonian matrices: links to unit interval graphs; new efficient combinatorial recognition algorithm based on Similarity-First Search, a natural extension to weighted graphs of Lex-BFS; structural characterization by minimal forbidden substructures; and application to tractable instances of the Quadratic Assignment Problem. Robinsonian matrices are structured matrices that have been introduced in the 1950's by the archeologist W.S. Robinson for chronological dating of Egyptian graves. A symmetric matrix is said to be Robinsonian if its rows and columns can be simultaneously reordered in such a way that the entries are monotone nondecreasing in the rows and columns when moving toward the main diagonal. Robinsonian matrices can be seen as a matrix analog of unit ...

05C62 ; 05C85 ; 68R10

Multi angle  Random hyperbolic graphs
Kiwi, Marcos (Auteur de la Conférence) | CIRM (Editeur )

Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree distribution. We will give a slow pace introduction to RHG, explain why they have attracted a fair amount of attention and then survey most of what is known about this promising infant model of real-world networks. Random hyperbolic graphs (RHG) were proposed rather recently (2010) as a model of real-world networks. Informally speaking, they are like random geometric graphs where the underlying metric space has negative curvature (i.e., is hyperbolic). In contrast to other models of complex networks, RHG simultaneously and naturally exhibit characteristics such as sparseness, small diameter, non-negligible clustering coefficient and power law degree ...

05C80 ; 68Q87 ; 74E35

The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a polynomial time algorithm to 3-color (or in general $k$-color) an $H$-free graph? 2) For which graphs $H$ are there finitely many 4-critical $H$-free graphs? This talk will survey recent progress on these questions, and in particular give a complete answer to the second one. The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a ...

05C15 ; 05C85

Nuage de mots clefs ici

Z