scientific article; zbMATH DE number 140476

MaRDI QIDQ4028894zbMATH OpenFDO

Authors Lin Chen

Publication date 28 March 1993

zbMATH Keywords

adjacency matrixcircular-arc graphcircular-arc representationgraph recognition problemmaximum cliquemaximum independent setminimum clique coverminimum dominating setNC algorithmsNP-completeparallel algorithmspolylogarithmic timepolynomially bounded processorssequential algorithms

Mathematics Subject Classification ID

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

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

(15)

• Circular-arc graphs with clique cover number two
• Linear time algorithms on circular-arc graphs
• Efficient parallel recognition of some circular arc graphs. I
• Optimal parallel algorithms on circular-arc graphs
• Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
• Revisiting Tucker's algorithm to color circular-arc graphs
• Polynomial time algorithms on circular-arc overlap graphs
• scientific article; zbMATH DE number 4215389 (Why is no real title available?)
• O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Independent Sets in Circular-Arc Graphs
• Parallel algorithms on circular-arc graphs
• Parallel algorithms on circular-arc graphs
• Optimal algorithms for computing articulation points and some related problems on a circular-arc graph
• Efficient parallel recognition of some circular arc graphs. II
• A constant factor approximation algorithm for boxicity of 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)