| |
|
|
|
|
|
|
|
|
1. |
Record Nr. |
UNISA996465391303316 |
|
|
Titolo |
Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 16th International Workshop WG '90, Berlin, Germany, June 20-22, 1990 / / edited by Rolf H. Möhring |
|
|
|
|
|
|
|
Pubbl/distr/stampa |
|
|
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1991 |
|
|
|
|
|
|
|
|
|
ISBN |
|
|
|
|
|
|
Edizione |
[1st ed. 1991.] |
|
|
|
|
|
Descrizione fisica |
|
1 online resource (XIII, 367 p.) |
|
|
|
|
|
|
Collana |
|
Lecture Notes in Computer Science, , 0302-9743 ; ; 484 |
|
|
|
|
|
|
Disciplina |
|
|
|
|
|
|
Soggetti |
|
Computers |
Algorithms |
Combinatorics |
Data structures (Computer science) |
Logic design |
Theory of Computation |
Algorithm Analysis and Problem Complexity |
Computation by Abstract Devices |
Data Structures |
Logic Design |
|
|
|
|
|
|
|
|
Lingua di pubblicazione |
|
|
|
|
|
|
Formato |
Materiale a stampa |
|
|
|
|
|
Livello bibliografico |
Monografia |
|
|
|
|
|
Note generali |
|
Bibliographic Level Mode of Issuance: Monograph |
|
|
|
|
|
|
Nota di contenuto |
|
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. |
|
|
|
|
|
|
Sommario/riassunto |
|
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. |
|
|
|
|
|
|
|
| |