Optimal circular arc representations: Properties, recognition, and construction

DOI10.1006/jcss.1998.1572zbMath0910.68092OpenAlexW1981682421MaRDI QIDQ1271617

Lin Chen

Publication date: 14 February 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1572

zbMATH Keywords

minimal interval

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient parallel recognition of some circular arc graphs. II
• Optimal parallel time bounds for the maximum clique problem on intervals
• Efficient parallel recognition of some circular arc graphs. I
• Faster optimal parallel prefix sums and list ranking
• Incidence matrices and interval graphs
• On the computational power of pushdown automata
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• A fast parallel algorithm for the maximal independent set problem
• Parallel Prefix Computation
• An Efficient Test for Circular-Arc Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Algorithms on circular-arc graphs
• The Parallel Evaluation of General Arithmetic Expressions
• Optimal bounds for decision problems on the CRCW PRAM
• Constructing a Maximal Independent Set in Parallel
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Optimal circular arc representations: Properties, recognition, and construction