Graph-theoretic concepts in computer science : 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993 : proceedings
Author(s)
Bibliographic Information
Graph-theoretic concepts in computer science : 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993 : proceedings
(Lecture notes in computer science, 790)
Springer-Verlag, c1994
- : gw
- : us
Available at 62 libraries
  Aomori
  Iwate
  Miyagi
  Akita
  Yamagata
  Fukushima
  Ibaraki
  Tochigi
  Gunma
  Saitama
  Chiba
  Tokyo
  Kanagawa
  Niigata
  Toyama
  Ishikawa
  Fukui
  Yamanashi
  Nagano
  Gifu
  Shizuoka
  Aichi
  Mie
  Shiga
  Kyoto
  Osaka
  Hyogo
  Nara
  Wakayama
  Tottori
  Shimane
  Okayama
  Hiroshima
  Yamaguchi
  Tokushima
  Kagawa
  Ehime
  Kochi
  Fukuoka
  Saga
  Nagasaki
  Kumamoto
  Oita
  Miyazaki
  Kagoshima
  Okinawa
  Korea
  China
  Thailand
  United Kingdom
  Germany
  Switzerland
  France
  Belgium
  Netherlands
  Sweden
  Norway
  United States of America
Note
Includes bibliographical references and index
"The 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '93)"--Pref
Description and Table of Contents
Description
This volume contains the proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '93, held near Utrecht, The Netherlands, in 1993.
The papers are grouped into parts on: hard problems on classes of graphs, structural graph theory, dynamic graph algorithms, structure-oriented graph algorithms, graph coloring, AT-free and chordal graphs, circuits and nets, graphs and interconnection networks, routing and shortest paths, and graph embedding and layout.
The 35 revised papers were chosen from 92 submissions after a careful refereeing process.
Table of Contents
Near-optimal dominating sets in dense random graphs in polynomial expected time.- Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality.- Hierarchically specified unit disk graphs.- Bounded tree-width and LOGCFL.- On reduction algorithms for graphs with small treewidth.- Algorithms and complexity of sandwich problems in graphs (extended abstract).- On-line graph algorithms for incremental compilation.- Average case analysis of fully dynamic connectivity for directed graphs.- Fully dynamic maintenance of vertex cover.- Dynamic algorithms for graphs with treewidth 2.- Short disjoint cycles in graphs with degree constraints.- Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs.- Towards a solution of the Holyer's problem.- Graphs, hypergraphs and hashing.- Coloring k-colorable graphs in constant expected parallel time.- Deciding 3-colourability in less than O(1.415n) steps.- A rainbow about T-colorings for complete graphs.- Approximating the chromatic polynomial of a graph.- Asteroidal triple-free graphs.- The parallel complexity of elimination ordering procedures.- Dually chordal graphs.- The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions.- Regular marked Petri nets.- The asynchronous committee meeting problem.- Gossiping in vertex-disjoint paths mode in interconnection networks.- The folded Petersen network: A new versatile multiprocessor interconnection topology.- Fast load balancing in Cayley graphs and in circuits.- Concurrent flows and packet routing in Cayley graphs (Preliminary version).- On multi-label linear interval routing schemes.- An 'All pairs shortest paths' distributed algorithm using 2n 2 messages.- Linear layouts of generalized hypercubes.- Graph ear decompositions and graph embeddings.- Improved bounds for the crossing numbers on surfaces of genus g.- Two algorithms for finding rectangular duals of planar graphs.- A more compact visibility representation.
by "Nielsen BookData"