Najbližší pondelok pokračujeme prednáškou Dávida Chalupu na tému hľadania pokrytia sietí klikami. Miesto a čas sa nemenia. Ing. David Chalupa (Ústav aplikovanej informatiky, FIIT STU) Construction of Near-optimal Vertex Clique Covering for Real-world Networks We will introduce a method based on combining a constructive and a bounding heuristic to solve the vertex clique covering problem (CCP). The aim of CCP is to partition the vertices of a graph into the smallest number of classes, which induce cliques. Searching for the solution to CCP is highly motivated by analysis of social and other real-world networks, applications in graph mining, as well as by the fact that CCP is one of the classical NP-hard problems. Combining the construction and the bounding heuristic helped us not only to find high-quality clique coverings but also to determine that in the domain of real-world networks, many of the obtained solutions are optimal, while the rest of them are near-optimal. In addition, the method has a polynomial time complexity and shows much promise for its practical use. Apart from experimental results, we will also shortly present some interesting theoretical results that explain how and why the approach works.
Posted on: Thu, 10 Oct 2013 13:13:37 +0000
Trending Topics
Recently Viewed Topics
© 2015