Author name cluster

Falk Hüffner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

TCS Journal 2018 Journal Article

Parameterized complexity of team formation in social networks

Robert Bredereck
Jiehua Chen
Falk Hüffner
Stefan Kratsch

Given a task that requires some skills and a social network of individuals with different skills, the Team Formation problem asks to find a team of individuals that together can perform the task, while minimizing communication costs. Since the problem is NP-hard, we identify the source of intractability by analyzing its parameterized complexity with respect to parameters such as the total number of skills k, the team size l, the communication cost budget b, and the maximum vertex degree Δ. We show that the computational complexity strongly depends on the communication cost measure: when using the weight of a minimum spanning tree of the subgraph formed by the selected team, we obtain fixed-parameter tractability for example with respect to the parameter k. In contrast, when using the diameter as measure, the problem is intractable with respect to any single parameter; however, combining Δ with either b or l yields fixed-parameter tractability.

Details DOI

TCS Journal 2009 Journal Article

Isolation concepts for clique enumeration: Comparison and computational experiments

Falk Hüffner
Christian Komusiewicz
Hannes Moser
Rolf Niedermeier

We do computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques (“isolated maximal” vs “maximal isolated”). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter “degree of isolation”. We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G n, m, p model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks.

Details DOI

TCS Journal 2009 Journal Article

Isolation concepts for efficiently enumerating dense subgraphs

Christian Komusiewicz
Falk Hüffner
Hannes Moser
Rolf Niedermeier

In an undirected graph G = ( V, E ), a set of k vertices is called c -isolated if it has less than c ⋅ k outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all c -isolated maximal cliques in O ( 4 c ⋅ c 4 ⋅ | E | ) time. We extend this to enumerating all maximal c -isolated cliques (which are a superset) and improve the running time bound to O ( 2. 8 9 c ⋅ c 2 ⋅ | E | ), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s -plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s -plex is the parameter and a fixed-parameter algorithm for enumerating isolated s -plexes when the parameter describes the degree of isolation.

Details DOI