Search

In this paper, we present a new method for detecting overlapping communities in networks with a predefined number of clusters called LPAM (Link Partitioning Around Medoids). The overlapping communities in the graph are obtained by detecting the disjoint communities in the associated line graph employing link partitioning and partitioning around medoids which are done through the use of a distance function defined on the set of nodes. We consider both the commute distance and amplified commute distance as distance functions. The performance of the LPAM method is evaluated with computational experiments on real life instances, as well as synthetic network benchmarks. For small and medium-size networks, the exact solution was found, while for large networks we found solutions with a heuristic version of the LPAM method. [ABSTRACT FROM AUTHOR]

Necessary and sufficient conditions for a cographic matroid having no two special matroids as minors to be signed-graphic are provided. The characterization utilizes the notion of Fournier triples of cocircuits and the recent excluded-minor characterization for regular signed-graphic matroids. [ABSTRACT FROM AUTHOR]

A matroid M has all-graphic cocircuits if M ∖ Y is a graphic matroid for every cocircuit Y ∈ C ∗ ( M ) . In Papalamprou and Pitsoulis (2013) it has been shown that signed-graphic matroids that are representable in G F ( 2 ) can be decomposed into graphic matroids and matroids with all-graphic cocircuits. In this paper we study this class of signed-graphic matroids with all-graphic cocircuits and provide the set of regular excluded minors as well as a complete characterization when the matroid is cographic, which in turn results in a simple recognition algorithm. [ABSTRACT FROM AUTHOR]

In this paper we employ Tutte's theory of bridges to derive a decomposition theorem for binary matroids arising from signed graphs. The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not based on κ-sums but rather on the operation of deletion of a cocircuit. Specifically, it is shown that certain minors resulting from the deletion of a cocircuit of a binary matroid will be graphic matroids, apart from exactly one that will be signed-graphic, if and only if the matroid is signed-graphic. [ABSTRACT FROM AUTHOR]

Abstract: We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix by finding node-edge incidence matrices and such that . Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called -sums starting from network matrices and their transposes and two compact representation matrices of a certain ten element matroid. Given that are binet matrices we examine the -sums of network and binet matrices. It is shown that the-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for . A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under -sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the -sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix. [Copyright &y& Elsevier]

Describes Fortran subroutines for finding approximate solutions of sparse instances of the Quadratic Assignment Problem using a Greedy randomized Adaptive Search Procedure. Description of the design; Use of the subroutines; Relationship between the increase in speed with the sparsity of data.

Recognition algorithms determining whether a given matroid is binary signed-graphic or not are presented in this work. Depending on whether the input is a cographic, a binary or a general matroid different algorithms are provided utilizing mainly decomposition results for the class of signed-graphic matroids. Finally, in order to devise such algorithms, necessary results regarding the representability of signed-graphic matroids in various fields are also given. [ABSTRACT FROM AUTHOR]

This work investigates two branch and bound algorithms based on different tree representations of the multidimensional assignment problem (MAP). The MAP may be depicted as either an index-based tree in which every level of the tree represents a different value of the first index or as a permutation-based tree that has vertices representing different permutation vectors of a feasible solution. We also look at the benefits of sorting the cost coefficients on each index tree level, performing a local search on either just the initial solution or every time we find a better solution, and attempting to use characteristics of previous good solutions through path relinking. The number of dimensions and the number of elements in each dimension will affect algorithm performance. We demonstrate the benefits and drawbacks of using different modifications to the branch and bound approach on different sizes of MAP instances. [ABSTRACT FROM AUTHOR]