New clique and independent set algorithms for circle graphs

DOI10.1016/0166-218X(92)90200-TzbMath0794.05120MaRDI QIDQ1186158

Susanne E. Hambrusch, Mikhail J. Atallah, Alberto Apostolico

Publication date: 28 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

maximum independent setmaximum cliqueefficient algorithmscircle graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

On the computational complexity of 2-interval pattern matching problems ⋮ Longest increasing subsequences in sliding windows ⋮ Computing the all-pairs longest chains in the plane ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ Efficient all path score computations on grid graphs ⋮ A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ Minimum vertex cover in rectangle graphs ⋮ Circular-arc graph coloring: On chords and circuits in the meeting graph ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ An output sensitive algorithm for computing a maximum independent set of a circle graph ⋮ The longest almost-increasing subsequence ⋮ Fast distance multiplication of unit-Monge matrices

Cites Work

• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• A decomposition theorem for partially ordered sets
• A priority queue in which initialization and queue operations takeO(loglogD) time
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Finding maximum cliques in circle graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Algorithms on circular-arc graphs
• A fast algorithm for computing longest common subsequences
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New clique and independent set algorithms for circle graphs