Pregunta:
¿cómo puede la restricción de conectividad para un subgrafo, que es inducida por un subconjunto apropiado $W\subset V$ de los vértices de $G(V,E),\ |V|=n,\ |W|=m$ formularse en un $LP$ ou $ILP$ ?
Fijar el tamaño del subgrafo es trivial; también algunos límites superiores en el número de aristas entre los elementos de $W$ puede concebirse con bastante facilidad. Sin embargo, no se me ocurre una condición necesaria y suficiente demostrable.
Parece que la Sección 3 de Algoritmos para el peso máximo conectado k -inducido de máximo peso (Ernst Althaus, Markus Blumenstock, Alexej Disterhoft, Andreas Hildebrandt y Markus Krupp; COCOA 2014) contiene varios modelos posibles de ILP.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
