JPH0520124A - 有向グラフの変換装置 - Google Patents
有向グラフの変換装置Info
- Publication number
- JPH0520124A JPH0520124A JP3168555A JP16855591A JPH0520124A JP H0520124 A JPH0520124 A JP H0520124A JP 3168555 A JP3168555 A JP 3168555A JP 16855591 A JP16855591 A JP 16855591A JP H0520124 A JPH0520124 A JP H0520124A
- Authority
- JP
- Japan
- Prior art keywords
- directed graph
- index
- node
- bdd
- nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Landscapes
- Debugging And Monitoring (AREA)
- Stored Programmes (AREA)
Abstract
(57)【要約】
【目的】 有向グラフのノードに適切にインデックスを
割り当てることにより、ＢＤＤ表現における使用ノード
数を削減することができ、従来に較べて記憶効率の向上
を図ることのできる有向グラフの変換装置を提供する。 【構成】 入力部１からインデックス割り当て部３に変
換対象となる有向グラフが入力されると、記憶部２内の
評価関数ｆによって最適のインデックス割り当てを選択
し、有向グラフの各ノードに、この最適のインデックス
割り当てる。そして、最適のインデックスを割り当てた
有向グラフを変換部４へ送り、変換部４でこの有向グラ
フをＢＤＤ表現に変換する。
割り当てることにより、ＢＤＤ表現における使用ノード
数を削減することができ、従来に較べて記憶効率の向上
を図ることのできる有向グラフの変換装置を提供する。 【構成】 入力部１からインデックス割り当て部３に変
換対象となる有向グラフが入力されると、記憶部２内の
評価関数ｆによって最適のインデックス割り当てを選択
し、有向グラフの各ノードに、この最適のインデックス
割り当てる。そして、最適のインデックスを割り当てた
有向グラフを変換部４へ送り、変換部４でこの有向グラ
フをＢＤＤ表現に変換する。
Description
【０００１】
【産業上の利用分野】本発明は、状態グラフ等の有向グ
ラフをＢＤＤ表現に変換する有向グラフの変換装置に関
する。
ラフをＢＤＤ表現に変換する有向グラフの変換装置に関
する。
【０００２】
【従来の技術】一般に、ソフトウェア構築等のため、何
らかの組合せ的な性質を持つ対象を表現する場合、複数
のノードと、これらのノードを結び付けるエッジとによ
って表現する有向グラフを用いると、分かりやすい表現
が得られる場合が多い。例えば、並行プログラムの検証
においては、プログラムの挙動を有向グラフの一種であ
る状態グラフで表現することが多い。
らかの組合せ的な性質を持つ対象を表現する場合、複数
のノードと、これらのノードを結び付けるエッジとによ
って表現する有向グラフを用いると、分かりやすい表現
が得られる場合が多い。例えば、並行プログラムの検証
においては、プログラムの挙動を有向グラフの一種であ
る状態グラフで表現することが多い。
【０００３】しかしながら、ここで問題になるのは、取
り扱うプログラムが大規模になる従って、生成される状
態グラフ等の有向グラフも大規模になり、非常に扱いに
くくなることである。そこで、大規模な有向グラフを、
より効率的に表現し記憶する必要性が出てくる。
り扱うプログラムが大規模になる従って、生成される状
態グラフ等の有向グラフも大規模になり、非常に扱いに
くくなることである。そこで、大規模な有向グラフを、
より効率的に表現し記憶する必要性が出てくる。
【０００４】このような有向グラフの効率的な記憶法の
一つとして、従来からＢＤＤ（Binary Decision Diagra
m ）による方法（以下、ＢＤＤ法と呼ぶ）が知られてお
り、広く用いられている。
一つとして、従来からＢＤＤ（Binary Decision Diagra
m ）による方法（以下、ＢＤＤ法と呼ぶ）が知られてお
り、広く用いられている。
【０００５】このようなＢＤＤ法によって有向グラフを
記憶する場合、予め有向グラフの各ノードに対してノー
ド識別のためにインデックスを割り当て、このインデッ
クスを用いて有向グラフをＢＤＤ表現に変換し、記憶す
る。なお、ここで、インデックスの割り当てとは、有向
グラフの各ノードに整数値を割り当てることをいう。こ
の割り当てにおいて、どのノードにどのインデックスを
割り当てるかについては、従来特に決まりはなく、例え
ばランダムにインデックスの割り当てを行っている。
記憶する場合、予め有向グラフの各ノードに対してノー
ド識別のためにインデックスを割り当て、このインデッ
クスを用いて有向グラフをＢＤＤ表現に変換し、記憶す
る。なお、ここで、インデックスの割り当てとは、有向
グラフの各ノードに整数値を割り当てることをいう。こ
の割り当てにおいて、どのノードにどのインデックスを
割り当てるかについては、従来特に決まりはなく、例え
ばランダムにインデックスの割り当てを行っている。
【０００６】
【発明が解決しようとする課題】しかしながら、上述し
た方法において、有向グラフの各ノードに対するインデ
ックスの割り当て方によって、ＢＤＤ表現において必要
となるノード数は大きく左右される。例えば、図３およ
び図４は、同一の有向グラフを示すものであり、インデ
ックスの割り当て方のみが異なっている。なお、これら
の図において、四角形で表された各ノード内に示された
数字がインデックスであり、この場合、ノード数が11で
あるため、各インデックスは4 桁の2 進数で表されてい
る。
た方法において、有向グラフの各ノードに対するインデ
ックスの割り当て方によって、ＢＤＤ表現において必要
となるノード数は大きく左右される。例えば、図３およ
び図４は、同一の有向グラフを示すものであり、インデ
ックスの割り当て方のみが異なっている。なお、これら
の図において、四角形で表された各ノード内に示された
数字がインデックスであり、この場合、ノード数が11で
あるため、各インデックスは4 桁の2 進数で表されてい
る。
【０００７】これらをＢＤＤ表現としたのが図５（図３
の有向グラフ）および図６（図４の有向グラフ）であ
る。この時、図５の場合の使用ノード数が44であるのに
対し図６の場合の使用ノード数は38である。したがっ
て、図４のようにインデックスを割り当てると、より記
憶効率がよいことが分かる。
の有向グラフ）および図６（図４の有向グラフ）であ
る。この時、図５の場合の使用ノード数が44であるのに
対し図６の場合の使用ノード数は38である。したがっ
て、図４のようにインデックスを割り当てると、より記
憶効率がよいことが分かる。
【０００８】上述した例は、サイズの小さい有向グラフ
の場合であるが、より大規模な有向グラフにおいては、
インデックスの割り当て方がＢＤＤ法の記憶効率に与え
る影響がより顕著になる。
の場合であるが、より大規模な有向グラフにおいては、
インデックスの割り当て方がＢＤＤ法の記憶効率に与え
る影響がより顕著になる。
【０００９】本発明は、かかる従来の事情に対処してな
されたもので、有向グラフのノードに適切にインデック
スを割り当てることにより、ＢＤＤ表現における使用ノ
ード数を削減することができ、従来に較べて記憶効率の
向上を図ることのできる有向グラフの変換装置を提供し
ようとするものである。
されたもので、有向グラフのノードに適切にインデック
スを割り当てることにより、ＢＤＤ表現における使用ノ
ード数を削減することができ、従来に較べて記憶効率の
向上を図ることのできる有向グラフの変換装置を提供し
ようとするものである。
【００１０】
【課題を解決するための手段】すなわち、本発明の有向
グラフの変換装置は、有向グラフを構成する各ノード
に、整数値を識別のためのインデックスとして割り当
て、このインデックスを用いて該有向グラフをＢＤＤ表
現に変換する有向グラフの変換装置であって、前記有向
グラフを入力するための入力手段と、前記各ノードに割
り当てたインデックスの組が、前記有向グラフの形態に
対してどの程度規則性を有するかを評価するための評価
関数を記憶する記憶手段と、前記入力手段から入力され
た前記有向グラフについてのインデックスを、前記記憶
手段内の前記評価関数を用いて評価して、前記有向グラ
フの形態に対する規則性が最も強くなるインデックスの
割り当て方を選択し、前記有向グラフの各ノードにイン
デックスを割り当てるインデックス割り当て手段と、前
記インデックス割り当て手段によって割り当てられたイ
ンデックスに基づいて、前記入力手段から入力された前
記有向グラフをＢＤＤ表現に変換する変換手段とを具備
したことを特徴とする。
グラフの変換装置は、有向グラフを構成する各ノード
に、整数値を識別のためのインデックスとして割り当
て、このインデックスを用いて該有向グラフをＢＤＤ表
現に変換する有向グラフの変換装置であって、前記有向
グラフを入力するための入力手段と、前記各ノードに割
り当てたインデックスの組が、前記有向グラフの形態に
対してどの程度規則性を有するかを評価するための評価
関数を記憶する記憶手段と、前記入力手段から入力され
た前記有向グラフについてのインデックスを、前記記憶
手段内の前記評価関数を用いて評価して、前記有向グラ
フの形態に対する規則性が最も強くなるインデックスの
割り当て方を選択し、前記有向グラフの各ノードにイン
デックスを割り当てるインデックス割り当て手段と、前
記インデックス割り当て手段によって割り当てられたイ
ンデックスに基づいて、前記入力手段から入力された前
記有向グラフをＢＤＤ表現に変換する変換手段とを具備
したことを特徴とする。
【００１１】
【作用】本発明の有向グラフの変換装置では、有向グラ
フのノード数に応じて多数通り考えられるインデックス
割り当て（インデックスの組）に対し、それらが有向グ
ラフの形態に対する規則性をどの程度持っているかを評
価関数によって評価し、最も強い規則性を持つインデッ
クスの割り当て方を選択する。
フのノード数に応じて多数通り考えられるインデックス
割り当て（インデックスの組）に対し、それらが有向グ
ラフの形態に対する規則性をどの程度持っているかを評
価関数によって評価し、最も強い規則性を持つインデッ
クスの割り当て方を選択する。
【００１２】これにより、ＢＤＤ表現における使用ノー
ド数を削減することができ、従来に較べて記憶効率の向
上を図ることができる。
ド数を削減することができ、従来に較べて記憶効率の向
上を図ることができる。
【００１３】
【実施例】以下、本発明の詳細を図面を参照して一実施
例について説明する。
例について説明する。
【００１４】図１は本発明の一実施例の構成を示すもの
で、図において１は有向グラフを入力するための入力
部、２は予め設定した評価関数ｆが格納されている記憶
部、３は記憶部２内の評価関数ｆによって最適のインデ
ックス割り当てを選択するインデックス割り当て部、４
はインデックス割り当て部３によって割り当てられたイ
ンデックスに基づいて、有向グラフをＢＤＤ表現に変換
する変換部である。
で、図において１は有向グラフを入力するための入力
部、２は予め設定した評価関数ｆが格納されている記憶
部、３は記憶部２内の評価関数ｆによって最適のインデ
ックス割り当てを選択するインデックス割り当て部、４
はインデックス割り当て部３によって割り当てられたイ
ンデックスに基づいて、有向グラフをＢＤＤ表現に変換
する変換部である。
【００１５】上記構成の有向グラフの変換装置では、図
２のフローチャートに示すように、入力部１からインデ
ックス割り当て部３に変換対象となる有向グラフが入力
されると（１００）、まず、記憶部２内の評価関数ｆに
よって最適のインデックス割り当てを選択し（１０
１）、有向グラフの各ノードに、この最適のインデック
ス割り当てる（１０２）。
２のフローチャートに示すように、入力部１からインデ
ックス割り当て部３に変換対象となる有向グラフが入力
されると（１００）、まず、記憶部２内の評価関数ｆに
よって最適のインデックス割り当てを選択し（１０
１）、有向グラフの各ノードに、この最適のインデック
ス割り当てる（１０２）。
【００１６】そして、最適のインデックスを割り当てた
有向グラフを変換部４へ送り（１０３）、変換部４でこ
の有向グラフをＢＤＤ表現に変換する（１０４）。
有向グラフを変換部４へ送り（１０３）、変換部４でこ
の有向グラフをＢＤＤ表現に変換する（１０４）。
【００１７】なお変換部４における有向グラフのＢＤＤ
表現への変換は、従来からコンピュータを用いて行われ
ている変換と同様にして行われる。また、変換部４で変
換されたＢＤＤ表現のグラフは、図示しない記憶装置等
に送られ記憶される。
表現への変換は、従来からコンピュータを用いて行われ
ている変換と同様にして行われる。また、変換部４で変
換されたＢＤＤ表現のグラフは、図示しない記憶装置等
に送られ記憶される。
【００１８】以下、上記有向グラフの変換装置の処理手
順をさらに詳細に説明する。まず、評価関数ｆの設定方
法について説明する。
順をさらに詳細に説明する。まず、評価関数ｆの設定方
法について説明する。
【００１９】対象とする有向グラフｇのノード数をＮ、
エッジ数をＥとした場合に、 Ｘ＝２Y ≧Ｎ （Ｘ，Ｙ：整数） ……（１） なる最小のＸに対する整数集合｛０，…，Ｘ｝をインデ
ックスの集合とする。
エッジ数をＥとした場合に、 Ｘ＝２Y ≧Ｎ （Ｘ，Ｙ：整数） ……（１） なる最小のＸに対する整数集合｛０，…，Ｘ｝をインデ
ックスの集合とする。
【００２０】有向グラフｇの各ノードに、このインデッ
クスの集合｛０，…，Ｘ｝のインデックスを割り当てる
割り当て方は全部で Ｘ！／（Ｘ−Ｎ）！ ……（２） 通りとなる。これら全ての割り当てを ｗi （ｉ＝１．…，Ｘ！／（Ｘ−Ｎ）！） とし、各割り当てｗi に対する評価関数として、 ｆ＝ｆ（ｗi ） （ｉ＝１，…，Ｘ！／（Ｘ−Ｎ）！） ……（３） を定義する。
クスの集合｛０，…，Ｘ｝のインデックスを割り当てる
割り当て方は全部で Ｘ！／（Ｘ−Ｎ）！ ……（２） 通りとなる。これら全ての割り当てを ｗi （ｉ＝１．…，Ｘ！／（Ｘ−Ｎ）！） とし、各割り当てｗi に対する評価関数として、 ｆ＝ｆ（ｗi ） （ｉ＝１，…，Ｘ！／（Ｘ−Ｎ）！） ……（３） を定義する。
【００２１】この評価関数ｆは、割り当てｗi の有向グ
ラフの形態（グラフのノードとエッジの様子）に対する
規則性の度合を表すものである。規則性として何を取り
上げるかは、扱う有向グラフの形態の特徴を考慮して適
宜選択する必要がある。本実施例では、以下有向グラフ
の形態に関するインデックス割り当ての規則性を「全エ
ッジの向きの偏り具合」として説明する。なお、ここ
で、有向グラフＧのノード数Ｎが10、エッジ数Ｅが22の
場合について説明する。
ラフの形態（グラフのノードとエッジの様子）に対する
規則性の度合を表すものである。規則性として何を取り
上げるかは、扱う有向グラフの形態の特徴を考慮して適
宜選択する必要がある。本実施例では、以下有向グラフ
の形態に関するインデックス割り当ての規則性を「全エ
ッジの向きの偏り具合」として説明する。なお、ここ
で、有向グラフＧのノード数Ｎが10、エッジ数Ｅが22の
場合について説明する。
【００２２】まず、エッジの向きを定義する。（１）式
において、この場合Ｎ＝10であるからＸ＝16，Ｙ＝4 で
あり、与えられるインデックスの集合は｛0 ，…，16｝
である。これを２進数表現とするとインデックスの集合
は｛0000，0001，0010，…，1111｝となる（Ｙ＝4 桁の
2 進数の集合）。
において、この場合Ｎ＝10であるからＸ＝16，Ｙ＝4 で
あり、与えられるインデックスの集合は｛0 ，…，16｝
である。これを２進数表現とするとインデックスの集合
は｛0000，0001，0010，…，1111｝となる（Ｙ＝4 桁の
2 進数の集合）。
【００２３】ここで、ある割り当てｗi によりノードｎ
1 、ｎ2 にインデックス0010、0011が与えられた場合、
ノードｎ1 、ｎ2 の位置ベクトルをそれぞれ（0 ，0 ，
1 ，0 ）、（0 ，0 ，1 ，1 ）とする。さらに、ノード
ｎ1 、ｎ2 の位置ベクトルの差ベクトル （0 ，0 ，1 ，1 ）−（0 ，0 ，1 ，0 ）＝（0 ，0 ，
0 ，1 ） を、ｎ1 からｎ2 へのエッジｅの向きとする。このよう
にして、割り当てｗi によるグラフＧの全てのエッジの
向きが求められる。
1 、ｎ2 にインデックス0010、0011が与えられた場合、
ノードｎ1 、ｎ2 の位置ベクトルをそれぞれ（0 ，0 ，
1 ，0 ）、（0 ，0 ，1 ，1 ）とする。さらに、ノード
ｎ1 、ｎ2 の位置ベクトルの差ベクトル （0 ，0 ，1 ，1 ）−（0 ，0 ，1 ，0 ）＝（0 ，0 ，
0 ，1 ） を、ｎ1 からｎ2 へのエッジｅの向きとする。このよう
にして、割り当てｗi によるグラフＧの全てのエッジの
向きが求められる。
【００２４】有向グラフＧに割り当てｗ1 によりインデ
ックスが割り当てられたとき、22本の各エッジｅ1 、
…、ｅ22の向きをｖ1 、…、ｖ22とし、
ックスが割り当てられたとき、22本の各エッジｅ1 、
…、ｅ22の向きをｖ1 、…、ｖ22とし、
【００２５】
【式１】
【００２６】
【００２７】とする。このｆ（ｗi ）が、割り当てｗi
による全エッジの偏り具合を表す評価関数である。ｆ
（ｗi ）の値が小さいほど偏り具合は大きい。
による全エッジの偏り具合を表す評価関数である。ｆ
（ｗi ）の値が小さいほど偏り具合は大きい。
【００２８】図１の記憶部２には、予め設定されたこの
ような評価関数ｆ（ｗi ）が記憶されている。なお、上
記説明では、各ノードに割り当てたインデックスを位置
ベクトルとして、有向グラフの形態に依存したインデッ
クスの割り当ての規則性を評価する評価関数ｆ（ｗi ）
について説明したが、例えばハイパーキューブ等を用い
て規則性を評価することもできる。
ような評価関数ｆ（ｗi ）が記憶されている。なお、上
記説明では、各ノードに割り当てたインデックスを位置
ベクトルとして、有向グラフの形態に依存したインデッ
クスの割り当ての規則性を評価する評価関数ｆ（ｗi ）
について説明したが、例えばハイパーキューブ等を用い
て規則性を評価することもできる。
【００２９】そして、入力部１から有向グラフＧが入力
されると、インデックス割り当て部３は、記憶部２内に
記憶された評価関数ｆ（ｗi ）に従って、有向グラフｇ
の各ノードにインデックスを割り当てる。
されると、インデックス割り当て部３は、記憶部２内に
記憶された評価関数ｆ（ｗi ）に従って、有向グラフｇ
の各ノードにインデックスを割り当てる。
【００３０】ここで、全ての割り当てｗi （ｉ＝１．
…，Ｘ！／（Ｘ−Ｎ）！）に対し、その評価関数の値ｆ
wi＝ｆ（ｗi ）を求め、ｆwiの値が最小になる割り当て
ｗi を求めることは、大規模な有向グラフを扱う場合、
Ｎの値が大きくなるため膨大な計算量を要する。そこ
で、インデックス割り当て部３は、周知の近似解法（例
えばアニーリング法、山登り法等）により、評価関数ｆ
wiの値が最小となる割り当てｗi を近似的に求めるよう
構成されている。そして、この近似解法によって求めた
最適な割り当てｗi に従って、有向グラフｇの各ノード
にインデックスを割り当てる。
…，Ｘ！／（Ｘ−Ｎ）！）に対し、その評価関数の値ｆ
wi＝ｆ（ｗi ）を求め、ｆwiの値が最小になる割り当て
ｗi を求めることは、大規模な有向グラフを扱う場合、
Ｎの値が大きくなるため膨大な計算量を要する。そこ
で、インデックス割り当て部３は、周知の近似解法（例
えばアニーリング法、山登り法等）により、評価関数ｆ
wiの値が最小となる割り当てｗi を近似的に求めるよう
構成されている。そして、この近似解法によって求めた
最適な割り当てｗi に従って、有向グラフｇの各ノード
にインデックスを割り当てる。
【００３１】各ノードにインデックスを割り当てられた
有向グラフｇは、この後、変換部４に送られる。そし
て、変換部４では、各ノードに割り当てられたインデッ
クスに基づいて、従来方法と同様な手順で有向グラフｇ
をＢＤＤ表現に変換する。
有向グラフｇは、この後、変換部４に送られる。そし
て、変換部４では、各ノードに割り当てられたインデッ
クスに基づいて、従来方法と同様な手順で有向グラフｇ
をＢＤＤ表現に変換する。
【００３２】表１に、ノード数10、エッジ数22の有向グ
ラフＭ１（前出のＧ）と、ノード数55、エッジ数90の有
向グラフＭ２に対し、従来法によるランダムにインデッ
クス割当を行った場合と、上記実施例による場合とで、
ＢＤＤ法による記憶効率（使用ノード数）の相違を比較
して示す。なお、従来法による場合は、それぞれランダ
ムに5 回インデックス割り当てを行った結果を示す。
ラフＭ１（前出のＧ）と、ノード数55、エッジ数90の有
向グラフＭ２に対し、従来法によるランダムにインデッ
クス割当を行った場合と、上記実施例による場合とで、
ＢＤＤ法による記憶効率（使用ノード数）の相違を比較
して示す。なお、従来法による場合は、それぞれランダ
ムに5 回インデックス割り当てを行った結果を示す。
【００３３】
【表１】
【００３４】表１に示すように、本実施例によれば、従
来に較べてＢＤＤ表現におけるノード数を低減すること
ができ、記憶効率の向上を図ることができる。
来に較べてＢＤＤ表現におけるノード数を低減すること
ができ、記憶効率の向上を図ることができる。
【００３５】
【発明の効果】以上説明したように、本発明の有向グラ
フの変換装置によれば、有向グラフのノードに適切にイ
ンデックスを割り当てることにより、ＢＤＤ表現におけ
る使用ノード数を削減することができ、従来に較べて記
憶効率の向上を図ることができる。
フの変換装置によれば、有向グラフのノードに適切にイ
ンデックスを割り当てることにより、ＢＤＤ表現におけ
る使用ノード数を削減することができ、従来に較べて記
憶効率の向上を図ることができる。
【図１】本発明の一実施例の有向グラフの変換装置の構
成を示す図である。
成を示す図である。
【図２】図１の有向グラフの変換装置の動作を示すフロ
ーチャートである。
ーチャートである。
【図３】インデックスを割り当てた有向グラフの例を示
す図である。
す図である。
【図４】インデックスを割り当てた有向グラフの例を示
す図である。
す図である。
【図５】図３の有向グラフをＢＤＤ表現に変換した例を
示す図である。
示す図である。
【図６】図４の有向グラフをＢＤＤ表現に変換した例を
示す図である。
示す図である。
１ 入力部 ２ 記憶部 ３ インデックス割り当て部 ４ 変換部
Claims (1)
- 【特許請求の範囲】 【請求項１】 有向グラフを構成する各ノードに、整数
値を識別のためのインデックスとして割り当て、このイ
ンデックスを用いて該有向グラフをＢＤＤ表現に変換す
る有向グラフの変換装置であって、 前記有向グラフを入力するための入力手段と、 前記各ノードに割り当てたインデックスの組が、前記有
向グラフの形態に対してどの程度規則性を有するかを評
価するための評価関数を記憶する記憶手段と、 前記入力手段から入力された前記有向グラフについての
インデックスを、前記記憶手段内の前記評価関数を用い
て評価して、前記有向グラフの形態に対する規則性が最
も強くなるインデックスの割り当て方を選択し、前記有
向グラフの各ノードにインデックスを割り当てるインデ
ックス割り当て手段と、 前記インデックス割り当て手段によって割り当てられた
インデックスに基づいて、前記入力手段から入力された
前記有向グラフをＢＤＤ表現に変換する変換手段とを具
備したことを特徴とする有向グラフの変換装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3168555A JPH0520124A (ja) | 1991-07-10 | 1991-07-10 | 有向グラフの変換装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3168555A JPH0520124A (ja) | 1991-07-10 | 1991-07-10 | 有向グラフの変換装置 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0520124A true JPH0520124A (ja) | 1993-01-29 |
Family
ID=15870201
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3168555A Withdrawn JPH0520124A (ja) | 1991-07-10 | 1991-07-10 | 有向グラフの変換装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0520124A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07210570A (ja) * | 1994-01-25 | 1995-08-11 | Fuji Xerox Co Ltd | 有向グラフ編集処理装置 |
-
1991
- 1991-07-10 JP JP3168555A patent/JPH0520124A/ja not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07210570A (ja) * | 1994-01-25 | 1995-08-11 | Fuji Xerox Co Ltd | 有向グラフ編集処理装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Charikar et al. | Maximizing quadratic programs: Extending Grothendieck's inequality | |
| Trifunović et al. | Parallel multilevel algorithms for hypergraph partitioning | |
| US20200175361A1 (en) | Partitioning of deep learning inference with dynamic offloading | |
| Kolomvatsos et al. | Multi-criteria optimal task allocation at the edge | |
| Albers et al. | Online makespan minimization with parallel schedules | |
| CN111782383A (zh) | 任务分配方法、服务器、电子终端及计算机可读存储介质 | |
| US6389374B1 (en) | OBDD variable ordering using sampling based schemes | |
| CN108681484A (zh) | 一种任务的分配方法、装置及设备 | |
| US6928445B2 (en) | Cost conversant classification of objects | |
| US9996391B2 (en) | Parallel computer system, method of controlling parallel computer system, and recording medium | |
| CN114830088B (zh) | 用于对计算集群或云计算平台的资源节点执行资源调度的方法和装置 | |
| Zotov et al. | Resource allocation algorithm in data centers with a unified scheduler for different types of resources | |
| WO2018051696A1 (ja) | データ圧縮方法、データ圧縮装置、コンピュータプログラム及びデータベースシステム | |
| Kortsarz et al. | Generating low-degree 2-spanners | |
| Pettersson et al. | Multiobjective integer programming: Synergistic parallel approaches | |
| JP2020184235A (ja) | 情報処理装置、情報処理方法、及び情報処理プログラム | |
| Hung et al. | Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs | |
| JPH0520124A (ja) | 有向グラフの変換装置 | |
| CN107562542B (zh) | 分布式数据处理系统数据分区方法及装置 | |
| CN110908803B (zh) | 一种基于余弦相似度算法的作业分配方法 | |
| Ramesh et al. | Interactive multicriteria linear programming: an extension of the method of Zionts and Wallenius | |
| Di Gaspero et al. | Hybrid local search for constrained financial portfolio selection problems | |
| US8516029B1 (en) | Methods and apparatuses for solving graph Laplacians | |
| Rguez et al. | A grasp-based algorithm for virtual network embedding | |
| Drakengren et al. | Towards a complete classification of tractability in Allen's algebra |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19981008 |