ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 研究報告
  2. アルゴリズム(AL)
  3. 2014
  4. 2014-AL-148

最大クリーク問題の多項式時間的可解性の拡張の更なる改良

https://ipsj.ixsq.nii.ac.jp/records/101701
https://ipsj.ixsq.nii.ac.jp/records/101701
95c418e9-1693-4e4b-93f4-307ffe4fc5a1
名前 / ファイル ライセンス アクション
IPSJ-AL14148014.pdf IPSJ-AL14148014.pdf (463.4 kB)
 2100年1月1日からダウンロード可能です。
Copyright (c) 2014 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.
AL:会員:¥0, DLIB:会員:¥0
Item type SIG Technical Reports(1)
公開日 2014-06-06
タイトル
タイトル 最大クリーク問題の多項式時間的可解性の拡張の更なる改良
タイトル
言語 en
タイトル A Further Improved Extended Result on Polynomial-Time Solvability of the Maximum Clique Problem
言語
言語 jpn
資源タイプ
資源タイプ識別子 http://purl.org/coar/resource_type/c_18gh
資源タイプ technical report
著者所属
電気通信大学先進アルゴリズム研究ステーション/早稲田大学教育学部数学科
著者所属
電気通信大学先進アルゴリズム研究ステーション/科学技術振興機構 ERATO 湊離散構造処理系プロジェクト/東京工業大学大学院情報理工学研究科
著者所属
電気通信大学先進アルゴリズム研究ステーション/電気通信大学大学院情報理工学研究科
著者所属
電気通信大学先進アルゴリズム研究ステーション/電気通信大学大学院情報理工学研究科
著者所属(英)
en
The Advanced Algorithms Research Laboratory, The University of Electro-Communications / Department of Mathematics, School of Education, Waseda University
著者所属(英)
en
The Advanced Algorithms Research Laboratory, The University of Electro-Communications / JST ERATO Minato Discrete Structure Manipulation System Project / Graduate School of Information Science and Engineering, Tokyo Institute of Technology
著者所属(英)
en
The Advanced Algorithms Research Laboratory, The University of Electro-Communications / Graduate School of Informatics and Engineering, The University of Electro-Communications
著者所属(英)
en
The Advanced Algorithms Research Laboratory, The University of Electro-Communications / Graduate School of Informatics and Engineering, The University of Electro-Communications
著者名 中西, 裕陽 富田, 悦次 若月, 光夫 西野, 哲朗

× 中西, 裕陽 富田, 悦次 若月, 光夫 西野, 哲朗

中西, 裕陽
富田, 悦次
若月, 光夫
西野, 哲朗

Search repository
著者名(英) Hiroaki, Nakanishi Etsuji, Tomita Mitsuo, Wakatsuki Tetsuro, Nishino

× Hiroaki, Nakanishi Etsuji, Tomita Mitsuo, Wakatsuki Tetsuro, Nishino

en Hiroaki, Nakanishi
Etsuji, Tomita
Mitsuo, Wakatsuki
Tetsuro, Nishino

Search repository
論文抄録
内容記述タイプ Other
内容記述 NP 完全である最大クリーク問題に対し,“節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である.” ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.
論文抄録(英)
内容記述タイプ Other
内容記述 This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.
書誌レコードID
収録物識別子タイプ NCID
収録物識別子 AN1009593X
書誌情報 研究報告アルゴリズム(AL)

巻 2014-AL-148, 号 14, p. 1-8, 発行日 2014-06-06
Notice
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
出版者
言語 ja
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-21 11:06:34.127449
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3