Efficient algorithms for finding maximum cliques of an overlap graph

DOI10.1002/NET.3230200203MaRDI QIDQ3471882zbMATH OpenOpenAlexFDO

Authors Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, Toshio Fujisawa

Publication date 1990

Published in Networks (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1903/4483

zbMATH Keywords

maximum cliqueNP-completeoverlap graphpolynomial timetime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Maximum independent set and maximum clique algorithms for overlap graphs
• Polynomial time algorithms on circular-arc overlap graphs
• Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
• A parllel algorithm for finding a maximum weight clique of an interval graph
• New clique and independent set algorithms for circle graphs

Cited in

(13)

• The maximum clique problem
• Maximum independent set and maximum clique algorithms for overlap graphs
• Towards a comprehensive theory of conflict-tolerance graphs
• Fast distance multiplication of unit-Monge matrices
• Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
• Polynomial time algorithms on circular-arc overlap graphs
• Refined algorithms for hitting many intervals
• scientific article; zbMATH DE number 4076670 (Why is no real title available?)
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Finding maximum cliques in arbitrary and in special graphs
• Improved algorithms for largest cardinality 2-interval pattern problem

This page was built for publication: Efficient algorithms for finding maximum cliques of an overlap graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3471882)