An Asymptotic Approximation Scheme for Multigraph Edge Coloring

Sanders, Peter; Steurer, David

An Asymptotic Approximation Scheme for Multigraph Edge Coloring

Sanders, P., & Steurer, D. (2005). An Asymptotic Approximation Scheme for Multigraph Edge Coloring. In Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05) (pp. 897-906). Philadelphia, USA: SIAM.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-259E-2 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-259F-F

資料種別: 会議論文

ファイル

表示: ファイル

作成者

表示:

非表示:

作成者:
Sanders, Peter¹, 著者
Steurer, David¹, 著者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

内容説明

表示:

非表示:

キーワード: -

要旨: The edge coloring problem asks for assigning colors from a minimum number of colors to edges of a graph such that no two edges with the same color are incident to the same node. We give polynomial time algorithms for approximate edge coloring of multigraphs, i.e., parallel edges are allowed. The best previous algorithms achieve a fixed constant approximation factor plus a small additive offset. Our algorithms achieve arbitrarily good approximation factors at the cost of slightly larger additive term. In particular, for any $\epsilon>0$ we achieve a solution quality of $(1+\epsilon)\opt+\Oh{1/\epsilon}$. The execution times of one algorithm are independent of $\epsilon$ and polynomial in the number of nodes and the \emph{logarithm} of the maximum edge multiplicity.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2006-04-20出版: 2005

出版の状態: 出版

ページ: -

出版情報: Philadelphia, USA : SIAM

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 279135
その他: Local-ID: C1256428004B93B8-8D31C50979686514C1256FAC004D3661-SanSte2005

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05)

種別: 会議論文集

著者・編者:

所属:

出版社, 出版地: Philadelphia, USA : SIAM

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 897 - 906 識別子（ISBN, ISSN, DOIなど）: ISBN: 0-89871-585-7

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1