P: ¿Cuáles son los mejores algoritmos de partición de gráficos para gráficos grandes?
Una técnica que me gusta es correr una caminata aleatoria desde cada vértice.
Como punto de partida, divida los vértices en n particiones con un vértice en cada partición. Después de un paso de la caminata, unifique las particiones que incluyen cualquiera de los vértices en la caminata de un paso.
- ¿Qué tecnologías y algoritmos se usan comúnmente para la resolución de entidades basadas en una intersección de algunos atributos?
- ¿Se utiliza una estructura de datos de pila para algoritmos multirecursionales?
- Silicon Valley (serie de televisión): ¿Cuál es el ejemplo más cercano en la vida real al algoritmo de compresión de Pied Piper?
- ¿Cuáles son los 100 deben resolver preguntas de SPOJ?
- ¿Es posible desarrollar un algoritmo que pueda hacer predicciones perfectas en el mercado de valores?
Continuando en la caminata (bueno, camina en plural ya que tenemos n viajeros comenzando desde cada vértice). Para los próximos vértices de la caminata, repita la unificación.
Si el gráfico está desconectado, siempre habrá más de una partición.
Para encontrar las partes más conectadas de un gráfico, pondere el algoritmo para que los vértices más visitados resistan la unificación con otra partición que también tenga muchas visitas entre sus vértices.
Para gráficos grandes, puede elegir limitar la longitud de las caminatas. También puede detener una caminata cuando llegue a su punto de partida nuevamente. Otra variación es ejecutar el algoritmo más de una vez para verificar que los resultados sean consistentes.
Hay muchas variaciones, dependiendo de lo que intente descubrir.
