Efficient parallel recognition of some circular arc graphs. II
From MaRDI portal
Publication:675297
DOI10.1007/BF02523192zbMath0865.68092MaRDI QIDQ675297
Publication date: 6 March 1997
Published in: Algorithmica (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
Related Items
Optimal circular arc representations: Properties, recognition, and construction, A selected tour of the theory of identification matrices, Graph isomorphism and identification matrices: Sequential algorithms, ON THE POWER OF SOME PRAM MODELS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On a circle-cover minimization problem
- Bipartite permutation graphs
- Parallel recognition and decomposition of two terminal series parallel graphs
- Optimal parallel time bounds for the maximum clique problem on intervals
- Efficient parallel recognition of some circular arc graphs. I
- Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
- Incidence matrices and interval graphs
- Matrix characterizations of circular-arc graphs
- Parallel recognition of the consecutive ones property with applications
- Minimum Cuts for Circular-Arc Graphs
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- The Complexity of Coloring Circular Arcs and Chords
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- Efficient parallel algorithms for bipartite permutation graphs