An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
From MaRDI portal
Recommendations
- Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
- An output sensitive algorithm for computing a maximum independent set of a circle graph
- Efficiently implementing maximum independent set algorithms on circle graphs
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- Algorithms and Computation
- Maximum weight independent set of circular-arc graph and its application
- An optimal algorithm for finding dominating cycles in circular-arc graphs
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
- Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
Cited in
(37)- Hadwiger's conjecture for proper circular arc graphs
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- Linear time algorithms on circular-arc graphs
- Finding a maximum set of independent chords in a circle
- Circular permutation graph family with applications
- Efficient parallel recognition of some circular arc graphs. I
- Finding a maximum matching in a circular-arc graph
- Optimal parallel algorithms on circular-arc graphs
- The maximum clique problem
- Optimal separable partitioning in the plane
- Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- On the complexity of the independent set problem in triangle graphs
- The complexity of dissociation set problems in graphs
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
- Polygon guarding with orientation
- An optimal algorithm to find centres and diameter of a circular-arc graph
- Stability in circular arc graphs
- Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
- A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
- Independent Sets in Circular-Arc Graphs
- Deferred-query—An efficient approach for problems on interval and circular-arc graphs
- Algorithms and Computation
- From a Circular-Arc Model to a Proper Circular-Arc Model
- Efficiently implementing maximum independent set algorithms on circle graphs
- Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
- A branch and bound algorithm for the maximum clique problem
- Parallel algorithms on circular-arc graphs
- Finding an approximate minimum-link visibility path inside a simple polygon
- Efficient parallel recognition of some circular arc graphs. II
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
- An output sensitive algorithm for computing a maximum independent set of a circle graph
- Efficient reduction for path problems on circular-arc graphs
- Finding maximum cliques in arbitrary and in special graphs
- Approximating minimum coloring and maximum independent set in dotted interval graphs
- Maximum weight independent set of circular-arc graph and its application
This page was built for publication: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3790662)
