Discrete Applied Mathematics, Volume 40

Volume 40, Number 1, 1992

Special Issue: Combinatorial Methods in VLSI

Thomas Andreae: Some Results on Visibility Graphs. 5-17 BibTeX
Ulrich Faigle, Rainer Schrader, György Turán: The Communication Complexity of Interval Orders. 19-28 BibTeX
Prabhakar Raghavan: Integer Programming in VLSI Design. 29-43 BibTeX
Stefan Voß: Steiner's Problem in Graphs: Heuristic Methods. 45-72 BibTeX
Dorothea Wagner, Frank Wagner: An Efficient Parallel Logarithmic Time Algorithm for the Channel Routing Problem. 73-81 BibTeX
Charlotte Wieners-Lummer: A Manhattan Channel Router with Good Theoretical and Practical Performance. 83-104 BibTeX

Foto N. Afrati: The Parallel Complexity of Single Rule Logic Programs. 107-126 BibTeX
János Demetrovics, Gyula O. H. Katona, Dezsö Miklós: Partial Dependencies in Relational Databases and their Realization. 127-138 BibTeX
János Demetrovics, Gyula O. H. Katona, Attila Sali: The Characterization of Branching Dependencies. 139-153 BibTeX
János Demetrovics, Leonid Libkin, Ilya B. Muchnik: Functional Dependencies in Relational Databases: A Lattice Point of View. 155-185 BibTeX
Georg Gottlob, Michael Schrefl, Markus Stumptner: Selective Inheritance of Attribute Values in Relational Databases. 187-216 BibTeX
Georg Lausen: Locking Based on a Pairwise Decomposition of the Transaction System. 217-236 BibTeX
Heikki Mannila, Kari-Jouko Räihä: On the Complexity of Inferring Functional Dependencies. 237-243 BibTeX
Yehoshua Sagiv, Yatin P. Saraiya: Minimizing Restricted-Fanout Queries. 245-264 BibTeX
Bernhard Thalheim: The Number of Keys in Relational and Nested Relational Databases. 265-282 BibTeX

Paul A. Catlin, Jerrold W. Grossman, Arthur M. Hobbs, Hong-Jian Lai: Fractional Arboricity, Strength, and Principal Partitions in Graphs and Matroids. 285-302 BibTeX
Israel Cederbaum, Israel Koren, Shmuel Wimer: Balanced Block Spacing for VLSI Layout. 303-318 BibTeX
Arundhati Raychaudhuri: Optimal Multiple Interval Assignments in Frequency Assignment and Traffic Phasing. 319-332 BibTeX
Stephen T. Schibell, Richard M. Stafford: Processor Interconnection Networks from Cayley Graphs. 333-357 BibTeX

Discrete Algorithms and Complexity

András Frank, Takao Nishizeki, Nobuji Saito, Hitoshi Suzuki: Algorithms for Routing around a Rectangle. 363-378 BibTeX
Naoki Katoh, Toshihide Ibaraki, Tiko Kameda: A Multiversion Cautious Scheduler with Dynamic Serialization Constraints for Database Concurrency Control. 379-395 BibTeX
Ming-Tat Ko, Y. T. Ching: Linear Time Algorithms for the Weighted Tailored 2-Partition Problem and the Weighted 2-Center Problem under l_infty-Distance. 397-410 BibTeX
Hsun-Ming Lee, Gerard J. Chang: Set to Set Broadcasting in Communication Networks. 411-421 BibTeX
Christos Levcopoulos, Ola Petersson: Matching Parentheses in Parallel. 423-431 BibTeX
Ruey-Der Lou, Majid Sarrafzadeh: Circular Permutation Graph Family with Applications. 433-457 BibTeX