#graph algorithms
6 resultsGraph Motif Problems Parameterized by Dual
Guillaume Fertin, Christian Komusiewicz
The paper investigates the computational complexity of three graph motif problems (GM, CGM, LGM) when parameterized by the dual parameter ℓ = |V| – |M|, providing both hardness res…
Parameterized Algorithms for Maximum Cut with Connectivity Constraints
Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi +1
The paper investigates two variants of the Maximum Cut problem that require additional connectivity conditions, proving their NP-completeness on several graph classes and presentin…
Efficient Algorithms for Densest Subgraph Discovery
Yixiang Fang, Kaiqiang Yu, Reynold Cheng +2
The paper introduces a new approach for finding densest subgraphs by leveraging k‑core structures, providing exact and approximate algorithms that work for various density definiti…
On the Relation of Strong Triadic Closure and Cluster Deletion
Niels Grüttemeier, Christian Komusiewicz
The paper analyzes the computational complexity of the Strong Triadic Closure and Cluster Deletion problems on undirected graphs, providing kernelization results, fixed-parameter a…
Greedy Rectilinear Drawings
Patrizio Angelini, Michael A. Bekos, Walter Didimo +6
The paper studies graph drawings where edges are axis-aligned (horizontal or vertical) and the drawing is greedy, meaning one can always move closer to a target vertex along a path…
Distributed Approximation Algorithms for Steiner Tree in the $\mathcal{CONGESTED}$ $\mathcal{CLIQUE}$
Parikshit Saikia, Sushanta Karmakar
The paper presents two deterministic distributed algorithms that approximate the Steiner tree problem in the CONGESTED CLIQUE model, providing trade‑offs between round and message…