One-dimensional logic gate assignment and interval graphs

DOI10.1109/TCS.1979.1084695MaRDI QIDQ3050329zbMATH OpenOpenAlexWikidataFDO

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

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)

Cited in

(22)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3050329)