Graph-theoretic concepts in computer science : 19th international workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993 : proceedings
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 algorith...
Bewaard in:
| Coauteur: | |
|---|---|
| Andere auteurs: | |
| Formaat: | Livre numérique |
| Taal: | Anglais |
| Gepubliceerd in: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Reeks: | Lecture notes in computer science
790 |
| Onderwerpen: | |
| Online toegang: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Opmerking: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Graph-theoretic concepts in computer science, 19th international workshop, WG '93, Utrecht, The Netherlands, June 16-18, 1993, proceedings, Jan van Leeuwen, ed, 1994, Berlin, Springer-Verlag, 1 vol. (IX-429 p.), Lecture notes in computer science, 3-540-57899-4 • Graph-Theoretic Concepts in Computer Science, Texte imprimé, 9783662199138 |
Inhoudsopgave:
- 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.