A lower bound on the area of permutation layouts | Zendy

Alok Aggarwal | Zendy; Maria Klawe | Zendy; David Lichtenstein | Zendy; Nathan Linial | Zendy; Avi Wigderson | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A lower bound on the area of permutation layouts

Author(s) -

Alok Aggarwal,

Maria Klawe,

David Lichtenstein,

Nathan Linial,

Avi Wigderson

Publication year - 1991

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/bf01759044

Subject(s) - permutation (music) , upper and lower bounds , combinatorics , theory of computation , mathematics , set (abstract data type) , discrete mathematics , computer science , algorithm , mathematical analysis , physics , acoustics , programming language

In this paper we prove a tight Ω(n 3) lower bound on the area of rectilinear grids which allow a permutation layout ofn inputs andn outputs. Previously, the best lower bound for the area of permutation layouts with arbitrary placement of the inputs and outputs was Ω(n 2), though Cutler and Shiloach [CS] proved an Ω(n 2.5) lower bound for permutation layouts in which the set of inputs and the set of outputs each lie on horizontal lines. Our lower bound also holds for permutation layouts in multilayer grids as long as a fixed fraction of the paths do not change layers.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research