Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Heuristics for the Maximum 2-layer RAC Subgraph Problem
verfasst von : Emilio Di Giacomo, Walter Didimo, Luca Grilli, Giuseppe Liotta, Salvatore A. Romeo
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.