One-dimensional logic gate assignment and interval graphs

DOI10.1109/TCS.1979.1084695zbMATH Open0414.94052OpenAlexW2089651609WikidataQ59445248 ScholiaQ59445248MaRDI QIDQ3050329FDOQ3050329

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)

• The \(k\)-neighbourhood-covering problem on interval graphs
• Computing the weighted isolated scattering number of interval graphs in polynomial time
• On minimal augmentation of a graph to obtain an interval graph
• Polynomial-time self-reducibility: theoretical motivations and practical results^∗
• Generating lower bounds for the linear arrangement problem
• Topological Bandwidth
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• Connections between cutting-pattern sequencing, VLSI design, and flexible machines
• 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
• An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs
• On minimizing width in linear layouts
• 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)