{'fraction_non_alphanumeric': 0.030467899891186073, 'fraction_numerical': 0.001088139281828074, 'mean_word_length': 4.508982035928144, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
One-dimensional logic gate assignment and interval graphs

This paper gives a graph-theoretic approach to the design of one-dimensional logic gate arrays using MOS or I/sup 2/L units. The incidence relation between gates and nets is represented by a graph H = (V, E), and a possible layout of gates and nets is characterized by an interval graph H = (V,E O F), where F is called an augmentation. It is shown that the number of tracks required for between-gate wiring is equal to the clique number (chromatic number) of H, and hence the optimum placement problem is converted to that of minimum clique number augmentation. This turns out to be an NP-complete problem. Instead a polynomial-time algorithm for finding a minimal augmentation is presented, where an augmentation is minimal if no proper subset of it is an augmentation. An algorithm for gate sequencing with respect to a given augmentation is also presented.