論文の概要: The Maximum Linear Arrangement Problem for trees under projectivity and
planarity
- arxiv url: http://arxiv.org/abs/2206.06924v2
- Date: Thu, 16 Jun 2022 12:31:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-19 03:36:52.248919
- Title: The Maximum Linear Arrangement Problem for trees under projectivity and
planarity
- Title(参考訳): 投影性と平面性を考慮した樹木の最大線形配置問題
- Authors: Llu\'is Alemany-Puig, Juan Luis Esteban and Ramon Ferrer-i-Cancho
- Abstract要約: 最大線形配置問題(MaxLA)は、グラフの$n$頂点から$D_pi(G)=sum_uvin E(G)|pi(u) - pi(v)|$を最大とする別の連続整数への写像である。
ここでは、木に対するPlanarとProjective MaxLAを解くために、$O(n)$-timeと$O(n)$-spaceアルゴリズムを示す。
- 参考スコア(独自算出の注目度): 0.90238471756546
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Maximum Linear Arrangement problem (MaxLA) consists of finding a mapping
$\pi$ from the $n$ vertices of a graph $G$ to distinct consecutive integers
that maximizes $D_{\pi}(G)=\sum_{uv\in E(G)}|\pi(u) - \pi(v)|$. In this
setting, vertices are considered to lie on a horizontal line and edges are
drawn as semicircles above the line. There exist variants of MaxLA in which the
arrangements are constrained. In the planar variant edge crossings are
forbidden. In the projective variant for rooted trees arrangements are planar
and the root cannot be covered by any edge. Here we present $O(n)$-time and
$O(n)$-space algorithms that solve Planar and Projective MaxLA for trees. We
also prove several properties of maximum projective and planar arrangements.
- Abstract(参考訳): 最大線形配置問題(MaxLA)は、グラフ$G$の$n$頂点から$D_{\pi}(G)=\sum_{uv\in E(G)}|\piを最大化する別の連続整数への写像$\pi$を求めることである。
(u)- \pi
(v)|$。
この設定では、頂点は水平線上にあり、辺は線上の半円として描かれる。
MaxLAには、アレンジを制約するバリエーションがある。
平面型エッジクロッシングは禁止されている。
根付き木の射影的変種では、配置は平面であり、根はどの辺でも覆えない。
ここでは、木に対するPlanarとProjective MaxLAを解くために、$O(n)$-timeと$O(n)$-spaceアルゴリズムを示す。
また、最大射影および平面配置のいくつかの性質も証明する。
関連論文リスト
- Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees [0.0]
最適二分分類木を設計するための2つのカットベース混合整数線形最適化(MILO)法を提案する。
我々のモデルは、最小限の実用不可能なサブシステム(MIS)をオンザフライで識別し、パッケージング制約の形をとる切断平面を導出する。
論文 参考訳(メタデータ) (2024-08-02T14:37:28Z) - Hierarchical cycle-tree packing model for $K$-core attack problem [0.0]
ここでは、この挑戦的な最適化問題に対して、階層的なサイクルツリーパッキングモデルを導入している。
統計物理学のレプリカ対称キャビティ法を用いて,このモデルを解析する。
関連する階層的サイクルツリー誘導攻撃(tt hCTGA)は、通常のランダムグラフに対するほぼ最適な攻撃解を構築することができる。
論文 参考訳(メタデータ) (2023-03-02T06:47:33Z) - SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。
Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
論文 参考訳(メタデータ) (2022-09-28T09:55:47Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳(メタデータ) (2021-09-10T07:01:15Z) - Minimum projective linearizations of trees in linear time [0.12289361708127873]
我々は、$O(n)$時間で疑いなく実行される射影的および平面的ケースに対して単純なアルゴリズムを導出する。
また、射影に制約のあるルート木の線形配置についても検討する。
論文 参考訳(メタデータ) (2021-02-05T16:35:38Z) - An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃
提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。
私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
論文 参考訳(メタデータ) (2020-10-22T10:59:49Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳(メタデータ) (2020-10-21T19:38:57Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳(メタデータ) (2020-10-13T17:26:09Z) - Bounds of the sum of edge lengths in linear arrangements of trees [0.90238471756546]
特に,固定サイズの木の縁長の和に関する諸問題について検討する。
一次元空間ネットワークにおける最適性スコアの研究のための基盤を確立した。
論文 参考訳(メタデータ) (2020-06-24T21:53:39Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳(メタデータ) (2020-05-18T14:23:09Z) - Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
そこで,MathcalS$ の目的 $min_textbfM は計量行列 $textbfM$ の凸微分可能な関数である。
Gershgorinディスクは、最初のeigenvector $textbfv$ of $textbfM$を使って完全に整列可能であることを証明します。
実験により, グラフ距離行列の計算効率は, 競合手法を用いて学習した指標よりも優れていた。
論文 参考訳(メタデータ) (2020-01-28T17:44:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。