Maximum independent set and related problems, with applications

摘要: This dissertation develops novel approaches to solving computationally difficult combinatorial optimization problems on graphs, namely maximum independent set, clique, graph coloring, minimum dominating sets and related problems. The application areas of the considered include information retrieval, classification theory, economics, scheduling, experimental design, computer vision among many others. The set are formulated as nonlinear programs, new methods for finding good quality approximate solutions in reasonable computational times introduced. All algorithms implemented successfully tested a number examples from diverse areas. proposed favorably compare with other competing approaches. A large part this is devoted detailed studies selected applications interest. Novel techniques analyzing structure financial markets based their network representation verified using massive data generated by U.S. stock markets. market cross-correlations price fluctuations instruments, provides valuable tool classifying instruments. In another application, exact values estimates size largest error correcting codes computed specially constructed graphs. Error lie heart digital technology, making cell phones, compact disk players modems possible. They also special significance due increasing importance reliability issues Internet transmissions. Finally, efficient construction virtual backbone wireless networks means connected problem unit-disk graphs developed tested.