Efficient parallel recognition of some circular arc graphs. I
From MaRDI portal
Publication:1209733
DOI10.1007/BF01190897zbMath0768.68127OpenAlexW4251188792MaRDI QIDQ1209733
Publication date: 16 May 1993
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01190897
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Related Items (6)
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ A selected tour of the theory of identification matrices
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On a circle-cover minimization problem
- Finding Hamiltonian circuits in proper interval graphs
- Dominating sets and domatic number of circular arc graphs
- Some parallel algorithms on interval graphs
- Parallel recognition and decomposition of two terminal series parallel graphs
- Finding maximum cliques on circular-arc graphs
- An optimal parallel algorithm for the minimum circle-cover problem
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- A parallel circle-cover minimization algorithm
- An optimal parallel circle-cover algorithm
- Faster optimal parallel prefix sums and list ranking
- Incidence matrices and interval graphs
- Matrix characterizations of circular-arc graphs
- Structure theorems for some circular-arc graphs
- Parallel recognition of the consecutive ones property with applications
- Minimum Cuts for Circular-Arc Graphs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- The NP-completeness column: an ongoing guide
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Parallel Merge Sort
- Stability in circular arc graphs
- Relations between Concurrent-Write Models of Parallel Computation
- Parallel Prefix Computation
- An Efficient Test for Circular-Arc Graphs
- Finding the maximum, merging, and sorting in a parallel computation model
- Efficient algorithms for interval graphs and circular-arc graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- The Complexity of Coloring Circular Arcs and Chords
- Algorithms on circular-arc graphs
- Coloring a Family of Circular Arcs
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
This page was built for publication: Efficient parallel recognition of some circular arc graphs. I
