✦ LIBER ✦

Greedily Finding a Dense Subgraph

✍ Scribed by Yuichi Asahiro; Kazuo Iwama; Hisao Tamaki; Takeshi Tokuyama

Book ID: 102572802
Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 144 KB
Volume: 34
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1062

No coin nor oath required. For personal study only.

✦ Synopsis

Given an n-vertex graph with nonnegative edge weights and a positive integer k F n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R Ž . 2 Ž y1 r3 . Ž . 2 of this greedy algorithm: 1r2

For k s nr2, for example, these bounds are 9r4 " Ž . O 1rn , improving on naive lower and upper bounds of 2 and 4, respectively.

📜 SIMILAR VOLUMES

A local algorithm for finding dense subg

A local algorithm for finding dense subgraphs

✍ Andersen, Reid 📂 Article 📅 2010 🏛 Association for Computing Machinery 🌐 English ⚖ 119 KB

Finding a monochromatic subgraph or a ra

Finding a monochromatic subgraph or a rainbow path

✍ András Gyárfás; Jenő Lehel; Richard H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

## Abstract For simple graphs __G__ and __H__, let __f__(__G__,__H__) denote the least integer __N__ such that every coloring of the edges of __K__~__N__~ contains either a monochromatic copy of __G__ or a rainbow copy of __H__. Here we investigate __f__(__G__,__H__) when __H__ = __P__~__k__~. We s

A decomposition of a graph into dense su

A decomposition of a graph into dense subgraphs

✍ Toida, S. 📂 Article 📅 1985 🏛 IEEE ⚖ 811 KB

A Linear-Time Algorithm for Finding a Ma

A Linear-Time Algorithm for Finding a Maximal Planar Subgraph

✍ Djidjev, Hristo N. 📂 Article 📅 2006 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 214 KB

A reduction method to find spanning Eule

A reduction method to find spanning Eulerian subgraphs

✍ Paul A. Catlin 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 621 KB

We ask, When does a graph G have a subgraph I' such that the vertices of odd degree in form a specified set S C V ( G ) , such that G -E(T) is connected? If such a subgraph can be found for a suitable choice of S, then this can be applied to problems such as finding a spanning eulerian subgraph of G

A Better Approximation Algorithm for Fin

A Better Approximation Algorithm for Finding Planar Subgraphs

✍ Gruia Călinescu; Cristina G Fernandes; Ulrich Finkler; Howard Karloff 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 321 KB

The MAXIMUM PLANAR SUBGRAPH problemᎏgiven a graph G, find a largest planar subgraph of Gᎏhas applications in circuit layout, facility layout, and graph drawing. No previous polynomial-time approximation algorithm for this NP-Complete problem was known to achieve a performance ratio larger than 1r3,