✦ LIBER ✦

Approximately counting cliques

✍ Scribed by Lars Eilstrup Rasmussen

Book ID: 101270673
Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 206 KB
Volume: 11
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199712)11:4<395::aid-rsa7>3.0.co;2-u

No coin nor oath required. For personal study only.

✦ Synopsis

We present a very simple, randomized approximation algorithm for determining the number of cliques in a random graph.

📜 SIMILAR VOLUMES

Fast algorithms for approximately counti

Fast algorithms for approximately counting mismatches

✍ Howard Karloff 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 640 KB

The complexity of approximately counting

The complexity of approximately counting stable matchings

✍ Prasad Chebolu; Leslie Ann Goldberg; Russell Martin 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 421 KB

Approximating Clique and Biclique Proble

Approximating Clique and Biclique Problems

✍ Dorit S. Hochbaum 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 317 KB

We present here 2-approximation algorithms for several node deletion and edge deletion biclique problems and for an edge deletion clique problem. The biclique problem is to find a node induced subgraph that is bipartite and complete. The objective is to minimize the total weight of nodes or edges de

An exact exponential time algorithm for

An exact exponential time algorithm for counting bipartite cliques

✍ Konstantin Kutzkov 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 152 KB

On Approximately Counting Colorings of S

On Approximately Counting Colorings of Small Degree Graphs

✍ Bubley, Russ; Dyer, Martin; Greenhill, Catherine; Jerrum, Mark 📂 Article 📅 1999 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 332 KB

The complexity of approximately counting

The complexity of approximately counting stable roommate assignments

✍ Prasad Chebolu; Leslie Ann Goldberg; Russell Martin 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 358 KB