Stability in circular arc graphs
From MaRDI portal
Publication:3796775
DOI10.1016/0196-6774(88)90023-5zbMath0651.68083OpenAlexW2057405567MaRDI QIDQ3796775
Peter L. Hammer, Martin Charles Golumbic
Publication date: 1988
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(88)90023-5
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone, Nerve complexes of circular arcs, Deferred-query—An efficient approach for problems on interval and circular-arc graphs, From a Circular-Arc Model to a Proper Circular-Arc Model, On the use of Boolean methods for the computation of the stability number, Maximum weight independent set of circular-arc graph and its application, New applications of clique separator decomposition for the maximum weight stable set problem, Algorithmic aspects of intersection graphs and representation hypergraphs, Succinct encodings for families of interval graphs, An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs, Optimization problems in dotted interval graphs, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, Struction revisited, Stability preserving transformations of graphs, Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms, Induced matchings in intersection graphs., Representations of graphs and networks (coding, layouts and embeddings), Boxicity of circular arc graphs, New results on induced matchings, Linear time algorithms on circular-arc graphs, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid, Irredundancy in circular arc graphs, Powers of cycles, powers of paths, and distance graphs, A note on \(\alpha\)-redundant vertices in graphs, Efficient parallel recognition of some circular arc graphs. I, Minimum vertex cover in rectangle graphs, Consensus algorithms for the generation of all maximal bicliques, On distance-3 matchings and induced matchings, Algorithms for clique-independent sets on subclasses of circular-arc graphs, Optimal pricing of capacitated networks, Partitioning a graph into convex sets, The clique operator on circular-arc graphs, Finding cut-vertices in the square roots of a graph, Graph transformations preserving the stability number, Optimal parallel algorithms on circular-arc graphs, Unnamed Item, On Distance-3 Matchings and Induced Matchings, Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Extending the MAX algorithm for maximum independent set, Independent packings in structured graphs, New sufficient conditions for \(\alpha\)-redundant vertices, The maximum independent set problem in subclasses of subcubic graphs, Finding maximum cliques in arbitrary and in special graphs, The maximum clique problem, Local transformations of graphs preserving independence number
