scientific article; zbMATH DE number 140476

MaRDI QIDQ4028894zbMATH OpenFDO

Authors Lin Chen

Publication date 28 March 1993

zbMATH Keywords

maximum cliqueadjacency matrixNP-completeparallel algorithmsmaximum independent setcircular-arc graphminimum dominating setminimum clique coverNC algorithmssequential algorithmspolylogarithmic timecircular-arc representationgraph recognition problempolynomially bounded processors

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Graph theory (05C99)

Recommendations

• Optimal parallel algorithms on circular-arc graphs
• scientific article; zbMATH DE number 4215389
• Efficient parallel recognition of some circular arc graphs. I
• Linear time algorithms on circular-arc graphs
• Efficient parallel recognition of some circular arc graphs. II

Cited in

(12)

• Polynomial time algorithms on circular-arc overlap graphs
• Independent Sets in Circular-Arc Graphs
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Efficient parallel recognition of some circular arc graphs. I
• Parallel algorithms on circular-arc graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Parallel algorithms on circular-arc graphs
• Revisiting Tucker's algorithm to color circular-arc graphs
• Efficient parallel recognition of some circular arc graphs. II
• Circular-arc graphs with clique cover number two
• Optimal parallel algorithms on circular-arc graphs
• Linear time algorithms on circular-arc graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4028894)