2012 | OriginalPaper | Chapter
Heuristics for the Maximum 2-layer RAC Subgraph Problem
Authors : Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta, Salvatore A. Romeo
Published in: WALCOM: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper studies 2-layer RAC drawings of bipartite graphs. The contribution is as follows: (
i
) We prove that the problem of computing the maximum 2-layer RAC subgraph is NP-hard even when the vertex ordering on one layer is fixed; this extends a previous NP-hardness result that allows the vertices to be permuted on each layer. (
ii
) We describe a 3-approximation algorithm for the maximum 2-layer RAC subgraph problem when the vertex ordering on each layer is not fixed, and a heuristic for the case that the vertex ordering on one of the layers is fixed. (
iii
) We present an experimental study that evaluates the effectiveness of the proposed approaches.