• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Student
Title
Supervisor
Faculty
Educational Programme
Final Grade
Year of Graduation
Albina Zamaletdinova
Search For Maximal Quasi - Triclique Using Mixed Integer Programming
2018
The problem of finding a maximum gamma-quasi-triclique is considered. Given a

tripartite undirected graph and a constant gamma, gamma from 0 to 1, a subset of

vertices is called a gamma-quasi-triclique if vertex induced subgraph has

dnsity at least gamma for a fixed gamma.

gamma-quasi-triclique can be countered as a relaxaion of a well-known triclique concept

for gamma = 1. This problem is NP-hard. In this work a maximum gamma-quasi-triclique

greedy algorithm was developed and tested. Also this problem was formulated

in the context of mixed integer programming and solved using IMB CPLEX

software. The results of two different approaches were compared on several realworld

datasets. While greedy algorithm finds optimal gamma-quasi-triclique in a shorter

time, the size of the triclique is always smaller than the one found by the mixed

integer programming approach.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses