Nicht aus der Schweiz? Besuchen Sie lehmanns.de

Graph-Theoretic Concepts in Computer Science

16th International Workshop WG '90, Berlin, Germany, June 20-22, 1990

Rolf H. Möhring (Herausgeber)

Buch | Softcover
XIII, 367 Seiten
1991 | 1991
Springer Berlin (Verlag)
978-3-540-53832-5 (ISBN)

Lese- und Medienproben

Graph-Theoretic Concepts in Computer Science -
CHF 74,85 inkl. MwSt
This volume gives the proceedings of WG '90, the 16th in a series of workshops. The aim of the workshop series is to contribute to integration in computer science by applying graph-theoretic concepts. The workshops are unusual in that they combine theoretical aspects with practice and applications. The volume is organized into sections on: - Graph algorithms and complexity, - VLSI layout, - Multiprocessor systems and concurrency, - Computational geometry, - Graphs, languages and databases, - Graph grammars. The volume contains revised versions of nearly all the papers presented at the workshop. Several papers take the form of preliminary reports on ongoing research.

Optimal parallel algorithms for sparse graphs.- Finding minimally weighted subgraphs.- On the complexity of some coloring games.- A generalized best-first search method in graphs.- Avoiding matrix multiplication.- Induced subraph isomorphism for cographs is NP-complete.- On feedback problems in planar digraphs.- Recognizing binary hamming graphs in O(n 2 log n) time.- Vertex-disjoint trees and boundary single-layer routing.- Bounds on the quality of approximate solutions to the group Steiner problem.- Two polynomial problems in PLA folding.- The VLSI layout problem in various embedding models.- Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems.- Deterministic message routing in faulty hypercubes.- On complexity of a message-routing strategy for multicomputer systems.- Embeddings of treelike graphs into 2-dimensional meshes.- Diagnosis of t/s-diagnosable systems.- Deciding 1-solvability of distributed task is NP-hard.- Remarks on some concurrency measures.- On the rectilinear art gallery problem algorithmic aspects.- Separation problems and circular arc systems.- Genus of orders and lattices.- Comparing the expressibility of two languages formed using NP-complete graph operators.- Decomposition of linear recursive logic programs.- On the transition graphs of automata and grammars.- Algebraic approach to graph transformation based on single pushout derivations.

Erscheint lt. Verlag 24.4.1991
Reihe/Serie Lecture Notes in Computer Science
Zusatzinfo XIII, 367 p.
Verlagsort Berlin
Sprache englisch
Maße 155 x 233 mm
Gewicht 621 g
Themenwelt Informatik Theorie / Studium Algorithmen
Mathematik / Informatik Mathematik Graphentheorie
Schlagworte Algorithm analysis and problem complexity • algorithms • Algorithmus • Automata • combinatorics • Complexity • Concurrency • Databases • data structures • Geometry • Graphentheorie • graph theory • Komplexität • Logic • Parallelität • Vertices • VLSI-Technologie • VLSI technology
ISBN-10 3-540-53832-1 / 3540538321
ISBN-13 978-3-540-53832-5 / 9783540538325
Zustand Neuware
Haben Sie eine Frage zum Produkt?
Mehr entdecken
aus dem Bereich
Interlingua zur Gewährleistung semantischer Interoperabilität in der …

von Josef Ingenerf; Cora Drenkhahn

Buch | Softcover (2023)
Springer Fachmedien (Verlag)
CHF 46,15