An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph

No abstract is available for this paper.

• Publication year

  1988

• Venue

  SIAM journal on computing (Print)

• Publication date

  1988-02-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/0217003
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Gate Matrix Layout

  1985cited by this paper

• A Stochastic Neuron Model for Finding a Near-Maximum Independent Set of a Circle Graph

  2016cites this paper
• K-Separator problem

  2014cites this paper
• Polygon guarding with orientation

  2014influential citation
• Improved Algorithms for the Connected Sensor Cover Problem December 10 , 2003

  2014cites this paper
• Computational Approaches To Anti-Toxin Therapies And Biomarker Identification

  2013cites this paper
• A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

  2013cites this paper
• On the complexity of the independent set problem in triangle graphs

  2011cites this paper
• The complexity of dissociation set problems in graphs

  2011cites this paper
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

  2011cites this paper
• The Hamiltonian Cycle Problem on Circular-Arc Graphs ∗

  2009cites this paper
• On the Complexity of Dissociation Set Problems in Graphs

  2009cites this paper
• Polynomial-time solvability of the maximum clique problem

  2009cites this paper
• An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs

  2009cites this paper
• From a Circular-Arc Model to a Proper Circular-Arc Model

  2008cites this paper
• Maximum independent set for intervals by divide and conquer with pruning

  2007cites this paper
• Uniformly optimal digraphs for strongly connected reliability

  2007cites this paper
• An Optimal Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

  2007cites this paper
• Approximating minimum coloring and maximum independent set in dotted interval graphs

  2006cites this paper
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm

  2006cites this paper
• Hadwiger's conjecture for proper circular arc graphs

  2006cites this paper
• A Linear Algorithm for the Connected Domination Problem on Circular-Arc Graphs

  2006cites this paper
• Maximum weight independent set of circular-arc graph and its application

  2006cites this paper
• Maximum Independent Set for Intervals by Divide-Prune-and-Conquer

  2005cites this paper
• Efficient parallel recognition of some circular arc graphs, I

  2005cites this paper
• Maximum Neural Network with Nonlinear Self-Feedback and Its Application to Maximum Independent Set Problem

  2005cites this paper
• Improved approximation algorithms for connected sensor cover

  2004cites this paper
• A simple linear algorithm for the connected domination problem in circular-arc graphs

  2004influential citation
• Powers of geometric intersection graphs and dispersion algorithms

  2002cites this paper
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone

  2002cites this paper
• Tesis de Licenciatura Problemas en grafos interseccion y overlap de arcos alrededor de un c¶‡rculo

  2001cites this paper
• Maintenance of a Piercing Set for Intervals with Applications

  2000cites this paper
• The Maximum Clique Problem

  1999cites this paper
• Computing Minimum Cut Sets for Circular-Arc Graphs | a New Approach

  1999cites this paper
• An Algorithm for Finding Maximal Common Subtopologies in a Set of Protein Structures

  1996cites this paper
• Disjoint Paths in Circular Arc Graphs

  1996cites this paper
• Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon

  1995cites this paper
• optimal Separable Partitioning in the Plane

  1995cites this paper
• On rectangle intersection and overlap graphs

  1995cites this paper
• Parallel Algorithms on Circular-arc Graphs

  1995cites this paper
• The maximum clique problem

  1994cites this paper
• Efficient parallel recognition of some circular arc graphs, II

  1993cites this paper
• Deferred-Query - An Efficient Approach for Problems on interval and Circular-Arc Graphs (Extended Abstract)

  1993cites this paper
• Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs

  1993cites this paper
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs

  1992cites this paper
• A parallel algorithm for maximum independent set of a circular-arc graph

  1992cites this paper
• An optimal algorithm for finding maximum induced bipartite subgraphs of circular-arc graphs

  1992cites this paper
• RNA Secondary Structure Prediction

  1992cites this paper
• Polynomial time algorithms on circular-arc overlap graphs

  1991cites this paper
• Linear Time Algorithms on Circular-Arc Graphs

  1991cites this paper
• Finding maximum cliques in arbitrary and in special graphs

  1991cites this paper
• Efficient reduction for path problems on circular-arc graphs

  1991cites this paper
• Finding Genes by Case-Based Reasoning in the Presence of Noisy Case Boundaries *

  1991cites this paper
• Case-Based Reasoning with Noisy Case Boundaries: An Application in Molecular Biology

  1990cites this paper
• A branch and bound algorithm for the maximum clique problem

  1990cites this paper
• Parallel algorithms for finding a near-maximum independent set of a circle graph

  1990cites this paper
• An O(n log n+m log log n) Maximum Weight Clique Algorithm for Circular-Arc Graphs

  1989cites this paper
• Optimal Parallel Algorithms on Circular-Arc Graphs

  1989cites this paper
• Linear Algorithms for Parity Path and Two Path Problems on Circular-Arc Graph

  1989cites this paper
• NC Algorithms for Circular-Arc Graphs

  1989cites this paper