A Correction to this paper has been published: https://doi.org/10.1007/s00224-021-10057-6

Abstract We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.

Clustering graph data has gained much attention in recent years, as data represented as graphs is ubiquitous in today's applications. For many applications, besides the mere graph data also further information about the vertices of a graph is available, which can be represented as attribute vectors. Recently, combined clustering approaches were introduced, which consider graph information and attribute vectors simultaneously for clustering. The visualization of clustering results can help users to get a better understanding of the results. In this paper, we introduce the GC-Viz system, which is implemented as a plugin for the Gephi platform. GC-Viz allows the user to test the combined clustering methods GAMer and DB-CSC on their data and to visualize and explore the clustering results. Furthermore, GC-Viz enables the user to visually compare the results of different clustering algorithms on the same dataset.