EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1318. Exact approaches for the colorful components problems
Invited abstract in session TC-29: Exact Algorithms and Formulations for Network Optimization Problems, stream Combinatorial Optimization.
Tuesday, 12:30-14:00Room: 157 (building: 208)
Authors (first author is the speaker)
| 1. | Martina Cerulli
|
| Computer Science Department, University of Salerno | |
| 2. | Claudia Archetti
|
| Università degli Studi di Brescia | |
| 3. | Carmine Sorgente
|
| Department of Mathematics, University of Salerno |
Abstract
Given a vertex-colored graph G, any connected component of G is said to be colorful if all its vertices have different colors. We address three problems related to these particular components of a graph, motivated by comparative genomics: the Colorful Components (CC), the Maximum Edges in transitive Closure (MEC), and the Minimum Colorful Components (MCC) problems.
In social networks, where nodes represent individuals and edges represent connections, all three problems can be used to determine the most influential connections linking distinct (colorful) and cohesive (connected) communities. By solving the CC problem, the risk of echo chambers is mitigated. Addressing the MEC problem means promoting the propagation of information through the community. Instead, the MCC problem helps prevent the isolation of users within small disconnected groups. When instead considering cyberspace networks of devices with various types of connections (e.g., permissions, data flow), identifying a subset of edges to remove while ensuring that the network remains in connected colorful components helps optimize the network's resilience to cyber threats.
We formulate the three problems as integer nonlinear programs, linearize them and propose families of valid inequalities. Furthermore, we provide bounds on the maximum number of colorful components at optimality and exploit them to reduce the size of the models. Benchmark instances are tested to evaluate the performances of the proposed models.
Keywords
- Combinatorial Optimization
- Graphs and Networks
Status: accepted
Back to the list of papers