Treffer: Some optimal parallel algorithms on interval and circular-arc graphs

Title:
Some optimal parallel algorithms on interval and circular-arc graphs
Authors:
HSU, F. R, SHAN, M. K, CHAO, H. S, LEE, R. C. T
Source:
Journal of information science and engineering. 21(3):627-642
Publisher Information:
Taipei: Institute of Information Science, Academia sinica, 2005.
Publication Year:
2005
Physical Description:
print, 18 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Algorithme parallèle, Parallel algorithm, Algoritmo paralelo, Arithmétique intervalle, Interval arithmetic, Aritmética intervalo, Calcul parallèle, Parallel computation, Cálculo paralelo, Code préfixe, Prefix code, Código prefijo, Equation Euler, Euler equation, Ecuación Euler, Graphe intervalle, Interval graph, Grafo intervalo, Interrogation base donnée, Database query, Interrogación base datos, Machine unique, Single machine, Máquina única, Modélisation, Modeling, Modelización, Plus court chemin, Shortest path, Camino más corto, Sommet graphe, Vertex(graph), Vértice grafo, Structure donnée, Data structure, Estructura datos, Suffixe, Suffix, Sufijo, Temps linéaire, Linear time, Tiempo lineal, Temps mise en oeuvre, Lead time, Tiempo puesta en marcha, EREW PRAM, all-pair shortest path, hinge vertex, interval graph, parallel algorithms
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Department of Information Engineering and Computer Science Feng Chia University, Taichung, 407, Tawain, Province of China
Department of Computer Science and Information Engineering National Chi Nan University, Nantou, 545, Tawain, Province of China
Department of Computer Science, National Chengchi University, Taipei, 116, Tawain, Province of China
Synopsys Taiwan Limited, Tawain, Province of China
ISSN:
1016-2364
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=16747945
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.16747945
Database:
PASCAL Archive

Weitere Informationen

In this paper, we consider some shortest path related problems on interval and circular-arc graphs. For the all-pair shortest path query problem on interval and circular-arc graphs, instead of using the sophisticated technique, we propose simple parallel algorithms using only the parallel prefix and suffix computations and the Euler tour technique. Our preprocessing algorithms run in O(log n) time using O(nlog n) processors. Using the data structure constructed by our preprocessing algorithms, a query of the length of a shortest path between any two vertices can be answered in constant time by using a single processor. For the hinge vertex problem on interval graphs, we propose an O(log n) time algorithm using O(nlog n) processors. It leads to a linear time sequential algorithm. Our algorithms work on the EREW PRAM model.