Optimal parallel time bounds for the maximum clique problem on intervals
From MaRDI portal
Publication:1198058
DOI10.1016/0020-0190(92)90239-RzbMath0772.68049WikidataQ128022083 ScholiaQ128022083MaRDI QIDQ1198058
Publication date: 16 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Related Items
Selection of programme slots of television channels for giving advertisement: a graph theoretic approach, Optimal computation of shortest paths on doubly convex bipartite graphs, Solving the shortest-paths problem on bipartite permutation graphs efficiently, Efficient parallel recognition of some circular arc graphs. II, Aliased register allocation for straight-line programs is NP-complete, A parallel algorithm to generate all maximal independent sets on permutation graphs, Optimal circular arc representations: Properties, recognition, and construction, PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS, OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS, ON THE POWER OF SOME PRAM MODELS
Cites Work
- The complexity of comparability graph recognition and coloring
- Faster optimal parallel prefix sums and list ranking
- A characterization of perfect graphs
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Parallel Merge Sort
- Parallel Prefix Computation
- Finding the maximum, merging, and sorting in a parallel computation model
- Optimal bounds for decision problems on the CRCW PRAM
