A partir do artigo de referência, estudar a propriedade de conexidade temporal em cliques, técnicas de remoção arestas sem que se perca tal propriedade e quais tipos de grafos admitem essas técnicas. Estudar os geradores temporais de grafos completos. Concluir trabalhando em cima das perguntas em aberto deixadas no final do artigo.
O estudo de objetos que mudam de estado ou configuração com o passar do tempo tem aplicações em diversas áreas da matemática e da computação, como sistemas dinâmicos, redes neurais, sistemas distribuídos e teoria de grafos. Por exemplo, quando dois computadores em uma rede recebem e enviam mensagens entre si, podemos representar os computadores como vértices e a conexão entre eles como uma aresta num instante t. Dessa forma, descrevemos a passagem de informação da rede seguindo a ordem de seus protocolos de troca de mensagens.
Assim, um grafo G possui um conjunto de vértices, um conjunto de arestas e uma aplicação que atribui a cada aresta um rótulo natural. Um grafo é temporalmente conexo se entre cada 2 vértices existir um caminho que segue uma ordem não decrescente dos rótulos entre eles. Um conjunto gerador de um grafo temporalmente conexo gera o grafo e preserva a conexidade temporal.
Dado um grafo denso com O(n²) arestas, queremos encontrar conjuntos geradores de ordem O(nlogn) e, se possível, de ordem O(n). Para isso, começamos estudando grafos completos e desenvolvemos técnicas para reduzir a quantidade de arestas sem perder as propriedades do grafo.
[1] CASTEIGTS, Arnaud; PETERS, Joseph G; SCHOETERS, Jason. Temporal cliques admit sparse spanners, Journal of Computer and System Sciences, Volume 121, 2021, Pages 1-17, ISSN 0022-0000