Del 790 - Lecture Notes in Computer Science

Graph-Theoretic Concepts in Computer Science

19th International Workshop, WG '93, Utrecht, The Netherlands, June 16 - 18, 1993. Proceedings

Häftad, Engelska, 1994

Av Jan van Leeuwen, Jan Van Leeuwen

709 kr

Beställningsvara. Skickas inom 10-15 vardagar

Fri frakt för medlemmar vid köp för minst 249 kr.

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.

Produktinformation

Utgivningsdatum1994-05-20
Mått155 x 235 x 25 mm
Vikt674 g
FormatHäftad
SpråkEngelska
SerieLecture Notes in Computer Science
Antal sidor437
Upplaga1994
FörlagSpringer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN9783540578994

Tillhör följande kategorier

Grafik och bildbehandling inom Data och it
Systemvetenskap och AI inom Data och it
Kombinatorik och grafteori inom Naturvetenskap och teknik
Diskret matematik inom Naturvetenskap och teknik
Programmeringsböcker inom Data och it
Tillämpad datateknik inom Data och it

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 ofgeneralized 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.