|
|
 |
|
Jeudi 5 Février
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Betweenness Centrality and Counting Problems |
| Description: |
Mehdi Naima Betweenness centrality (BC), introduced in 1977, is a fundamental measure of node importance in networks, widely used in fields ranging from sociology to computer science. BC quantifies the extent to which a node lies on shortest paths between pairs of nodes, making its computation closely tied to the enumeration of these paths. In this work, we investigate the computational complexity of determining BC for all nodes in a graph, highlighting the challenges associated with exhaustive shortest-path counting. We further examine extensions of BC to dynamic graphs, where edges carry temporal information and optimal paths are determined not only by topology but also by timing constraints (i.e., fastest paths). We explore the hardness of computing BC under such dynamic conditions and discuss how temporal dependencies complicate classical shortest-path approaches. Our study aims to unify understanding of BC computation across static and temporal graph models and to identify open problems in efficiently counting relevant paths in these settings. |
Jeudi 12 Février
| Heure: |
10:30 - 12:00 |
| Lieu: |
Salle A303, bâtiment A, Université de Villetaneuse |
| Résumé: |
Properties of matroids in picking games against Greedy |
| Description: |
Emiliano Lancini Given an hypergraph on a set of n ordered vertices, we define an independent set X to be
feasible, if X is a possible outcome for a player in a sequential picking game, against a greedy
adversary, where no hyperedge can be contained in the union of both outcomes. We prove that
testing feasibility is NP-complete, even if the hypergraph is a graph, but it becomes polynomial
(in n) for matroid hypergraphs, that is, when the hyperedges are the circuits of some matroid
(in which independence can be tested with an oracle). We prove also that optimizing a linear
function over feasible sets is NP-hard for graphs and matroid hypergraphs, even for graphic
matroids, but it becomes polynomial for laminar matroids. |
|
|
