Efficient algorithms for interval graphs and circular-arc graphs
From MaRDI portal
Publication:3956413
DOI10.1002/net.3230120410zbMath0493.68066MaRDI QIDQ3956413
No author found.
Publication date: 1982
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230120410
maximum independent set; maximum clique; minimum covering by disjoint completely connected sets of cliques
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
Related Items
Restrictions of graph partition problems. I, Representations of graphs and networks (coding, layouts and embeddings), Linear time algorithms on circular-arc graphs, New clique and independent set algorithms for circle graphs, Processor optimization for flow graphs, Maximum \(k\)-covering of weighted transitive graphs with applications, Efficient parallel recognition of some circular arc graphs. I, Optimal circular arc representations: Properties, recognition, and construction, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, The maximum clique problem, An exact algorithm for the maximum stable set problem, An approximation algorithm for the license and shift class design problem, The allocation problem in hardware design, On a 2-dimensional equipartition problem, Optimal separable partitioning in the plane, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, On powers of circular arc graphs and proper circular arc graphs, New results on induced matchings
