Accepted papers to WG '96

[Info on WG '96]

This is the list of accepted papers to WG '96. Papers do not
appear in a particular order in the list.

For more info on the workshop see the URL:
http://www.dis.uniroma1.it/wg96/

------------------------------------------------------------------------------
On $k$-Partitioning the $n$-Cube
Sergej L. Bezrukov

System diagnosis with smallest risk of error
Krzystof Diks, Andrzej Pelc

Efficient Union-Find for Planar Graphs and other Sparse Graph Classes
Jens Gustedt

Approximate Maxima Finding of Continuous Functions under Restricted
Budget
Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, David Peleg

Homogeneous Sets and Domination Problems
Falk Nicolai, Thomas Szymczak

LexBFS-orderings and power of graphs
Feodor F. Dragan, Falk Nicolai, Andreas Brandstaedt

More general parallel tree contraction: Register allocation and
broadcasting in a tree
Krzystof Diks, Torben Hagerup

Independent Spanning Trees of Product Graphs
Koji Obokata, Yukihiro Iwasaki, Feng Bao, Yoshihide Igarashi

On the Hardness of Allocating Frequencies for Hybrid Networks
Ewa Malesinska, Alessandro Panconesi

Detecting Diamond Necklaces in Labeled Dags (A Problem for
Distributed Debugging)
Michel Hurfin, Michel Raynal

Shortest Path Algorithms for Nearly Acyclic Directed Graphs
Tadao Takaoka

Improved Approximations of Independent Dominating Set in Bounded
Degree Graphs
Paola Alimonti, Tiziana Calamoneri

Modifying Networks to Obtain Low Cost Trees
S.O. Krumke, H. Noltemeier, M.V. Marathe, S.S. Ravi, K.U.
Drangmeister

Generalized Edge-Ranking of Trees
Xiao Zhou, Abul Kashem, Takao Nishizeki

Definability Equals Recognizability of Partial 3-Trees
Damon Kaller

Designing distance-preserving fault-tolerant topologies
Swamy K. Sitarama, Abdol-Hossein Esfahanian

A new characterization of P4-connected graphs
Luitpold Babel and Stephan Olariu

Counting edges in a Dag
Serafino Cicerone, Daniele Frigioni, Umberto Nanni, Francesco
Pugliese

On-Line Algorithms for Shortest Path Problems on Planar Digraphs
Hristo Djidjev

Algebraic Graph Derivations for Graphical Calculi
Wolfram Kahl

Optimal Parallel Routing in Star Graphs
C. C. Chen, J. Chen

Embedding Complete Binary Trees in Product Graphs
Antonio Fernandez, Adrienne Broadwater, Kemal Efe

One, Two, Three, Many, or: Complexity Aspects of Dynamic Network
Flows with Dedicated Arcs
Bettina Klinz, Gerhard J. Woeginger

Switchbox Routing in VLSI Design: Closing the Complexity Gap
Stephan Hartmann, Markus W. Schaeffter, Andreas S. Schulz

Upward Drawings of Search Trees
P. Crescenzi, P. Penna

Clique and anticlique partition of graphs
Krzysztof Brys, Zbigniew Lonc

The Optimal Cost Chromatic Partition Problem for Trees and Interval
Graphs
Leo G. Kroon, Arunabha Sen, Haiyong Deng, Asim Roy

Node rewriting in hypergraphs
Michel Bauderon, Helene Jacquet

Closure properties of context free hyperedge replacement systems
O. Ciotti, F. Parisi-Presicce

Computing Disjoint Path with Lenght Constraints
Spyros Tragoudas, Yaakov Varol