A generalization of Ripà’s square spiral solution for the n × n × ··· × n Points Upper Bound Problem. Additionally, we provide a non-trivial lower bound for the k-dimensional n_1 × n_2 × ··· × n_k Points Problem. In this way, we can build a range in which, with certainty, all the best possible … Read more
\(\) Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many … Read more
\(\) In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this … Read more
In this work, we compute the lower bound of the integrality gap of the Metric Steiner Tree Problem (MSTP) on a graph for some small values of number of nodes and terminals. After debating about some limitations of the most used formulation for the Steiner Tree Problem, namely the Bidirected Cut Formulation, we introduce a … Read more
A physical limitation in quantum circuit design is the fact that gates in a quantum system can only act on qubits that are physically adjacent in the architecture. To overcome this problem, SWAP gates need to be inserted to make the circuit physically realizable. The nearest neighbour compliance problem (NNCP) asks for an optimal embedding … Read more
The maximum independent set (MIS) seeks to find a subset of vertices with the maximum size such that no pair of its vertices are adjacent. This paper develops a recursive fixing procedure that generalizes the existing polytime algorithm to solve the maximum independent set problem on chordal graphs, which admit simplicial orderings. We prove that … Read more
\(\) The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only \( O(log(n)) \) bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate … Read more
\(\) A series-parallel matrix is a binary matrix that can be obtained from an empty matrix by successively adjoining rows or columns that are copies of an existing row/column or have at most one 1-entry. Equivalently, series-parallel matrices are representation matrices of graphic matroids of series-parallel graphs, which can be recognized in linear time. We … Read more
This paper presents two heuristic algorithms for the distance-based critical node problem (DCNP) that finds k nodes whose removal minimizes the pairwise connection within D hops in the remaining network. The structural properties of the complex networks have not yet been extensively addressed in the literature. Specifically, the community structure of complex networks needs to … Read more
One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node … Read more