論文の概要: One Color Preprocessing Improves DSATUR

• arxiv url: http://arxiv.org/abs/2609.17633v1
• Date: Tue, 15 Sep 2026 10:35:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.466434
• Title: One Color Preprocessing Improves DSATUR
• Title（参考訳）: 1色前処理によるDSATURの改善
• Abstract要約: SSLD(Semidefinite Spectral Learning with DSATUR)は、DSATURが与えられたグラフの残りの部分を完全に色づけする前に、最初の良い色クラスを前処理することで、DSATURを改善する。 DSATURに対するSSLDと、DIMACSインスタンス、ランダムグラフ(Erds-Rényi, Watts-Strogatz, Barabsi-Albert)、周波数割り当て、ジョブショップスケジューリングインスタンス上での1-color-classプリプロセッシングアルゴリズムに対するSSLDの評価を行った。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Graph Coloring Problem (GCP) is NP-hard and DSATUR stands as one of the fastest heuristics for it despite producing colorings that typically use more colors than state-of-the-art coloring algorithms. We propose SSLD (Semidefinite Spectral Learning with DSATUR), which improves DSATUR by preprocessing a first good color class before letting DSATUR complete coloring the rest of the given graph. We obtain this color class from a Semidefinite Programming (SDP), similar to an SDP used to compute the Lovász theta number. To the best of our knowledge, SSLD is the first approach to improve DSATUR by preprocessing through fixed color classes. We evaluate SSLD against DSATUR and against a naive 1-color-class preprocessing algorithm on DIMACS instances, random graphs (Erdős--Rényi, Watts-Strogatz, Barabási--Albert), Frequency Assignment and Job Shop Scheduling instances. SSLD matches or beats DSATUR in almost every case across over 1600 benchmark instances, and out performs the naive GISD baseline, allows us to confirm the value brought by the SDP-guided choice of the first color class. This quality comes at a runtime cost of roughly 195 times slower that DSATUR, but demonstrating that SDP-guided preprocessing of a first color class is a direction for future improvements.
• Abstract（参考訳）: グラフ着色問題(GCP)はNPハードであり、DSATURは最先端の着色アルゴリズムよりも多くの色を使用するのが一般的であるにもかかわらず、最も高速なヒューリスティックの1つである。 DSATURを用いたSSLD(Semidefinite Spectral Learning with DSATUR)を提案する。 このカラークラスは半有限計画法(SDP)から得られるもので、ロヴァース・テータ数を計算するのに使用されるSDPに似ている。 我々の知る限りでは、SSLDは固定色クラスを前処理することでDSATURを改善するための最初のアプローチである。 DSATURに対するSSLDと、DIMACSインスタンス、ランダムグラフ(エルデシュ-レニイ、ワッツ-ストロガッツ、バラバシ-アルベルト)、周波数アサインメント、ジョブショップスケジューリングインスタンス上の1色クラスの単純な前処理アルゴリズムに対するSSLDの評価を行った。 SSLDは1600以上のベンチマークインスタンスでほぼすべてのケースでDSATURと一致し、単純なGISDベースラインを実行します。 この品質は、DSATURの約195倍のランタイムコストで実現されているが、最初のカラークラスのSDP誘導前処理が将来の改善の方向性であることを実証している。

関連論文リスト

• Color and Frequency Correction for Image Colorization [0.8122270502556375]
  本研究は,既存の自己色化方向モデルDDColorに従って,画像カラー化の再最適化を行っている。 DDColorの既存の重みに関する実験では、周波数帯域に制限があり、入力寸法が不十分なことに起因するカラーキャスト問題があることが判明した。
  論文  参考訳（メタデータ） (2025-10-27T14:57:14Z)
• GenColorBench: A Color Evaluation Benchmark for Text-to-Image Generation Models [61.786094845872576]
  GenColorBenchは、テキストから画像までのカラー生成のための、最初の総合的なベンチマークである。 I SCC-NBS や CSS3/X11 などのカラーシステムにも採用されている。 400以上の色をカバーする44K色のプロンプトによって、知覚的および自動評価を通じてモデルの真の能力を明らかにする。
  論文  参考訳（メタデータ） (2025-10-23T14:12:55Z)
• SPDGAN: A Generative Adversarial Network based on SPD Manifold Learning for Automatic Image Colorization [1.1174586184779576]
  生成逆ネットワーク(SPDGAN)を用いたSymmetric Positive Definite (SPD) Manifold Learningに基づく完全自動カラー化手法を提案する。 本モデルは,2つの識別器とジェネレータの対角ゲームを確立する。その目標は,残差接続により層間の色情報を失うことなく,偽のカラー化画像を生成することである。
  論文  参考訳（メタデータ） (2023-12-21T00:52:01Z)
• DFormer: Rethinking RGBD Representation Learning for Semantic Segmentation [76.81628995237058]
  DFormerは、RGB-Dセグメンテーションタスクの転送可能な表現を学ぶための新しいフレームワークである。 ImageNet-1Kから画像深度ペアを使用してバックボーンを事前トレーニングする。 DFormerは2つのRGB-Dタスクで最先端のパフォーマンスを実現する。
  論文  参考訳（メタデータ） (2023-09-18T11:09:11Z)
• Improving Video Colorization by Test-Time Tuning [79.67548221384202]
  テスト時間チューニングによる映像の着色性向上を目的とした,効果的な手法を提案する。 提案手法は,テスト中に追加のトレーニングサンプルを構築するための基準を利用して,PSNRにおいて平均13dBの性能向上を実現している。
  論文  参考訳（メタデータ） (2023-06-25T05:36:40Z)
• Modulate Your Spectrum in Self-Supervised Learning [65.963806450552]
  ホワイトニング損失は、自己教師付き学習における特徴の崩壊に対する理論的保証を提供する。 埋め込みのスペクトルを変調するフレームワークであるスペクトル変換(ST)を導入する。 我々は、トレースロス(INTL)を持つIterNormという新しいSTインスタンスを提案する。
  論文  参考訳（メタデータ） (2023-05-26T09:59:48Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
  論文  参考訳（メタデータ） (2022-09-19T14:37:35Z)
• Towards Vivid and Diverse Image Colorization with Generative Color Prior [17.087464490162073]
  最近のディープラーニングベースの手法は、画像のカラー化を低コストで行うことができる。 我々は,事前学習されたGAN(Generative Adversarial Networks)にカプセル化されている,豊かで多様な色を活かして鮮やかな色を復元することを目的としている。 先進的なデザインと繊細なデザインの強力な生成色のおかげで、我々の手法は1つの前進パスで鮮やかな色を作り出すことができた。
  論文  参考訳（メタデータ） (2021-08-19T17:49:21Z)
• CoRe: Color Regression for Multicolor Fashion Garments [80.57724826629176]
  本稿では,RGBの正確な値を予測するために,色検出を回帰問題として扱う。 新たに提案したアーキテクチャの洗練のための第2のレグレッションステージも含んでいます。 このアーキテクチャはモジュラーであり、多色衣料のすべての色のRGBを検出するために容易に拡張される。
  論文  参考訳（メタデータ） (2020-10-06T16:12:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。