One-dimensional logic gate assignment and interval graphs

DOI10.1109/TCS.1979.1084695zbMath0414.94052OpenAlexW2089651609WikidataQ59445248 ScholiaQ59445248MaRDI QIDQ3050329

Ernest S. Kuh, Toshinobu Kashiwabara, Toshio Fujisawa, Tatsuo Ohtsuki, Hajimu Mori

Publication date: 1979

Published in: IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tcs.1979.1084695

zbMATH Keywords

interval graphNp-completealgorithm for gate sequencingdesign of one-dimensional logic gate arrays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Related Items (21)

An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs ⋮ Refinements on an enumeration scheme for solving a pattern sequencing problem ⋮ Generating lower bounds for the linear arrangement problem ⋮ Polynomial-time self-reducibility: theoretical motivations and practical results^∗ ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ A polynomial algorithm for weighted scattering number in interval graphs ⋮ Connections between cutting-pattern sequencing, VLSI design, and flexible machines ⋮ On minimal augmentation of a graph to obtain an interval graph ⋮ Linear placement algorithms and applications to VLSI design ⋮ Routing with critical paths ⋮ An optimal greedy heuristic to color interval graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Narrowness, pathwidth, and their application in natural language processing ⋮ An optimal parallel algorithm to construct a tree 3-spanner on interval graphs ⋮ An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs ⋮ Thek-neighbourhood-covering problem on interval graphs ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ On minimizing width in linear layouts ⋮ Computing the weighted isolated scattering number of interval graphs in polynomial time ⋮ An optimal parallel algorithm for computing cut vertices and blocks on interval graphs ⋮ Topological Bandwidth

This page was built for publication: One-dimensional logic gate assignment and interval graphs