Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Chemistry (10)
- Computer Sciences (4)
- Engineering (4)
- Electrical and Computer Engineering (3)
- Theory and Algorithms (3)
-
- VLSI and Circuits, Embedded and Hardware Systems (3)
- Analytical Chemistry (1)
- Biochemistry (1)
- Biochemistry, Biophysics, and Structural Biology (1)
- Computer Engineering (1)
- Environmental Chemistry (1)
- Life Sciences (1)
- Operations Research, Systems Engineering and Industrial Engineering (1)
- Organic Chemistry (1)
- Other Computer Engineering (1)
- Other Operations Research, Systems Engineering and Industrial Engineering (1)
- Keyword
-
- Chemistry (3)
- Air pollutants (1)
- Algorithms (1)
- Analytical Chemistry (1)
- Channel routing (1)
-
- Collaboration (1)
- Combinatorial problems (1)
- Computational complexity (1)
- Energy resources (1)
- Environmental assessment (1)
- Environmental legislation (1)
- Forest resources (1)
- Ionophores.;Nuclear magnetic resonance.;Chlorides in the body.;Biological transport.;Cystic fibrosis. (1)
- Lignite (1)
- Lithium;Lithium;Nuclear magnetic resonance spectroscopy.;Erythrocytes.;Phospholipids.;Lithium (1)
- Lower bounds (1)
- Organic compounds;Chirality.;Anions. (1)
- Palladium catalysts.;Oxidation. (1)
- Renewable energy (1)
- River routing (1)
- Routability (1)
- VLSI channel routing (1)
- VLSI layout (1)
- Water pollution (1)
- Publication
- Publication Type
Articles 1 - 14 of 14
Full-Text Articles in Physical Sciences and Mathematics
On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy
On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy
Computer Science: Faculty Publications and Other Works
We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.
Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh
Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh
Computer Science: Faculty Publications and Other Works
In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of “congestion” and “dilation” measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((Clg^ε(Nd)+Dlg(Nd))/lglg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also …
Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley
Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley
Computer Science: Faculty Publications and Other Works
We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.
Finding A Maximum-Density Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih
Finding A Maximum-Density Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case …
The Synthesis Of Chiral Building Blocks Using Beta-Hydroxy Sulfoxide Dianions, Carla M. Edwards
The Synthesis Of Chiral Building Blocks Using Beta-Hydroxy Sulfoxide Dianions, Carla M. Edwards
Master's Theses
No abstract provided.
Palladium(Ii) Catalysis, Glenn Noronha
Study Of The Hexamethylenetetramine, Ammonia, And Formaldehyde System: Quantitative Determinations, Gary Lee Madsen
Study Of The Hexamethylenetetramine, Ammonia, And Formaldehyde System: Quantitative Determinations, Gary Lee Madsen
Dissertations
No abstract provided.
Low Temperature Spectroscopic And Annealing Studies Of Disordered Organic Solids, Dwayne L. Labrake
Low Temperature Spectroscopic And Annealing Studies Of Disordered Organic Solids, Dwayne L. Labrake
Dissertations
No abstract provided.
Spin Label Studies Of Radical Reduction In Normal And Sickle Erythrocyte Membranes Associated With Antioxidants, Yin Zhang
Dissertations
No abstract provided.
Lithium Transport, Mg2+ Competition, And Phospholipid Composition In Human Erythrocytes: A Multinuclear Magnetic Resonance Study, Aida Abraha
Dissertations
No abstract provided.
Multinuclear Magnetic Resonance Study Of Chlorine And Cesium Ion Distribution In Human Erythrocyte Suspensions, Lisa Wittenkeller
Multinuclear Magnetic Resonance Study Of Chlorine And Cesium Ion Distribution In Human Erythrocyte Suspensions, Lisa Wittenkeller
Dissertations
No abstract provided.
A Proposal For United States/Polish Collaboration On Energy And The Environment, Carole B. Szpunar
A Proposal For United States/Polish Collaboration On Energy And The Environment, Carole B. Szpunar
Chemistry: Faculty Publications and Other Works
Argonne National Laboratory, a U.S. Department of Energy facility that is operated by the University of Chicago and located southwest of Chicago, Illinois, has proposed a collaborative effort by the United States and Poland to conduct applied research on energy and environmental topics of common interest. Through this collaboration, evaluative studies on energy and environmental assessment issues could be developed and implemented by Argonne and one or more sister institutions in Poland, which could lead to active research, development, and demonstration joint activities. The objective of this initiative is to produce strategies and options for review by Poland's decision makers …
Remote Dianions In The Synthesis Of Indolizidine Alkaloids, Diana L. C. Green Green
Remote Dianions In The Synthesis Of Indolizidine Alkaloids, Diana L. C. Green Green
Dissertations
No abstract provided.
Syntheses Of Azure-B Neuropeptide Conjugates And A Novel Bicyclic Triene, Milind D. Choubal
Syntheses Of Azure-B Neuropeptide Conjugates And A Novel Bicyclic Triene, Milind D. Choubal
Dissertations
No abstract provided.