Discrete System Theory and Large-Scale Optimization Methods Based on Binary Decision Diagrams and
Discrete System Theory and Large-Scale Optimization Methods Based on Binary Decision Diagrams and
批准号:
09480050
负责人:
IMAI Hiroshi
金额:
$9.47万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (B).
财政年份:
1997
资助国家:
日本
项目状态:
已结题
起止时间:
1997 至 2000
中文摘要
在本研究中,我们的目的是提出一个统一的方法,离散系统理论的基础上二叉决策图,并开发一个原型系统的统一系统。通过我们的结果,我们现在可以表示整个中等规模的离散结构,在一个隐式和紧凑的方式,这不能通过现有的方法。我们应用我们的方法来计算网络的可靠性,也计算琼斯多项式的结。这些计算问题是已知的#P-hard,但是,与我们的方法,中等规模的问题可以在实践中严格解决。例如,可以计算14 x14网格的网络可靠性函数。我们还探讨了二元判定图的基本理论,通过研究一个单调布尔函数直接表示和用它们的素蕴涵表示时的大小差异,并提出了新的方法,一种是基于代数方法,另一种是基于量子方法。关于代数方法,Grobner基充分研究网络流问题。关于量子方法,我们研究了二进制决策图的量子模拟,以研究量子计算的计算能力。这些新结果将很快公布。
英文摘要
In this research, we aimed at proposing a unified approach to discrete system theory based on binary decision diagrams, and developing a prototype system for the unified system. By our results, we can now represent the whole moderate-scale discrete structure in a implicit and compact manner, which could not be done by the existing methods. We applied our approach to network reliability computation and also computing the Jones polynomial of a knot. These computation problems are known to be #P-hard, but, with our methods, moderate-size problems can be solved rigorously in practice. For example, the network reliability function of a grid of 14x14 can be computed. We also explore fundamental theory of binary decision diagrams, by investigating the difference in size when a monotone Boolean function is represented directly and when it is represented by their prime implicants.New approaches have also been demonstrated, one is based on algebraic approach, and the other is based on quantum approach. Concerning the algebraic approach, Grobner bases are fully investigated for network flow problems. Concerning the quantum approach, we investigate a quantum analog of binary decision diagrams in order to investigate the computational power of quantum computing. These new results will be published soon.
期刊论文(44)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
K.Sekine and H.Imai: "Counting the Number of Paths in a Graph via BDDs"IEICE Transactions on Fundamentals. E80-A. 682-688 (1997)
K.Sekine 和 H.Imai:“通过 BDD 计算图中路径的数量”IEICE Transactions on Fundamentals。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
S.Fujishige, ed., H.Imai et al: "Discrete Structure and Algorithms V : Network Reliability Computation and Related Topics (in Japanese)"Kindai-kgaku-sha. 1-50 (1997)
S.Fujishige 编辑、H.Imai 等人:“离散结构和算法 V:网络可靠性计算和相关主题(日语)”Kindai-kgaku-sha。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
A.Tajima and H.Imai: "Computational Investigations of the Optimality of Two-and Three-Dimensional Triangulations under Several Criteria" Proceedings of the 10th Canadian Conference on Computational Geometry. 44-45 (1998)
A.Tajima 和 H.Imai:“若干标准下二维和三维三角剖分的最优性的计算研究”第十届加拿大计算几何会议论文集。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
F.Takeuchi and H.Imai: "Enumerating Triangulations for Products of Two Simplices and for Arbitrary Configurations of Points." Lecture Notes in Computer Science. Vol.1276. 470-481 (1997)
F.Takeuchi 和 H.Imai:“枚举两个单纯形乘积和任意点配置的三角剖分。”
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
M.Inaba,N.Katoh and H.Imai: "Variance-Based κ-Clustering Algorithms by Voronoi Diagrams and Randomization"IEICE Trans.Information and Systems. E83-D,6. 1199-1206 (2000)
M.Inaba、N.Katoh 和 H.Imai:“Voronoi 图和随机化的基于方差的 κ 聚类算法”IEICE Trans.Information and Systems,1199-1206 (2000)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 39 条
Computational Combinatorial Physics by Harmonizing Matroid Theory and Quantum Physics
-
批准号:16K12392
-
项目类别:Grant-in-Aid for Challenging Exploratory Research
-
资助金额:$2.16万
-
财政年份:2016
-
负责人:IMAI Hiroshi
-
依托单位:
Interaction between two motor domains of cytoplasmic dynein stepping along microtubules revealed by cryo-electron microscopy.
-
批准号:16K07327
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$3.16万
-
财政年份:2016
-
负责人:IMAI Hiroshi
-
依托单位:
Exploration of synthesis and outward acceleration of circumstellar matter through simultaneous multiple-band high-resolution radio imaging
-
批准号:16H02167
-
项目类别:Grant-in-Aid for Scientific Research (A)
-
资助金额:$29.87万
-
财政年份:2016
-
负责人:IMAI Hiroshi
-
依托单位:
Exploiting Matroid Minor Theory and Its Connection with Quantum Computing Models
-
批准号:26540004
-
项目类别:Grant-in-Aid for Challenging Exploratory Research
-
资助金额:$2.33万
-
财政年份:2014
-
负责人:IMAI Hiroshi
-
依托单位:
Large area sky surveys of hydroxyl maser sources and establishment of their high precision trigonometry
-
批准号:25610043
-
项目类别:Grant-in-Aid for Challenging Exploratory Research
-
资助金额:$2.5万
-
财政年份:2013
-
负责人:IMAI Hiroshi
-
依托单位:
High-Level Processing of Huge-Scale Networks: Challenges from Graph Decomposition Theory to Practically Efficient Algorithms
-
批准号:24650003
-
项目类别:Grant-in-Aid for Challenging Exploratory Research
-
资助金额:$2.5万
-
财政年份:2012
-
负责人:IMAI Hiroshi
-
依托单位:
Preservation of endangered and rare animalspecies using induced pluripotent stem cells.
-
批准号:23658224
-
项目类别:Grant-in-Aid for Challenging Exploratory Research
-
资助金额:$2.5万
-
财政年份:2011
-
负责人:IMAI Hiroshi
-
依托单位:
Unified Approach for Nanotechnology CAD/Computation by Algorithmic Analysis of Periodic Crystal Structures
-
批准号:22650002
-
项目类别:Grant-in-Aid for Challenging Exploratory Research
-
资助金额:$1.83万
-
财政年份:2010
-
负责人:IMAI Hiroshi
-
依托单位:
Long term culture and regulation of differentiation of germ cells from the testis in domestic species
-
批准号:22380150
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$12.65万
-
财政年份:2010
-
负责人:IMAI Hiroshi
-
依托单位:
Surveys and high resolution imaging of jets from evolved stars
-
批准号:20540234
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.75万
-
财政年份:2008
-
负责人:IMAI Hiroshi
-
依托单位:
Quantum-Classical Correlation Games and New Analyses of Discrete-Continuous Optimization and Computational Complexity
-
批准号:20300002
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$12.15万
-
财政年份:2008
-
负责人:IMAI Hiroshi
-
依托单位:
Optimization via Quantum Information Combinatorics and Its Applications to Extend Fundamentals of Quantum Information Science and Technology
-
批准号:17300001
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$10.53万
-
财政年份:2005
-
负责人:IMAI Hiroshi
-
依托单位:
Advanced Geometric Algorithms Based on Discrete Analysis of Information-Geometric Structures with Applications
-
批准号:13480079
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$9.47万
-
财政年份:2001
-
负责人:IMAI Hiroshi
-
依托单位:
NewDevelopments of Discrete-System Algorithmics Based on Complexes
-
批准号:10205204
-
项目类别:Grant-in-Aid for Scientific Research on Priority Areas (B)
-
资助金额:$6.98万
-
财政年份:1998
-
负责人:IMAI Hiroshi
-
依托单位:
Analysis of biological function of tenascin-C in progression of heart failure and its clinical application
-
批准号:10670644
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.43万
-
财政年份:1998
-
负责人:IMAI Hiroshi
-
依托单位:
Realization of Geographic Information Systems with High-Quality Processing Based on Computational Geometry
-
批准号:09558029
-
项目类别:Grant-in-Aid for Scientific Research (B).
-
资助金额:$8.19万
-
财政年份:1997
-
负责人:IMAI Hiroshi
-
依托单位:
Developments of Advanced Optimization Systems Unitying Discrete and Continuous Approaches Associate
-
批准号:07555615
-
项目类别:Grant-in-Aid for Scientific Research (B)
-
资助金额:$1.22万
-
财政年份:1995
-
负责人:IMAI Hiroshi
-
依托单位:
Joint Research on Algorithms in Computational Geometry
-
批准号:06044058
-
项目类别:Grant-in-Aid for international Scientific Research
-
资助金额:$4.1万
-
财政年份:1994
-
负责人:IMAI Hiroshi
-
依托单位:
Research on Algorithms for Discrete Optimization Problems with Dynamic and On-Line Environments.
-
批准号:05452122
-
项目类别:Grant-in-Aid for General Scientific Research (B)
-
资助金额:$4.1万
-
财政年份:1993
-
负责人:IMAI Hiroshi
-
依托单位:
Algorithms on continuous models for solving discrete problems and their parallelization.
-
批准号:03680026
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.28万
-
财政年份:1991
-
负责人:IMAI Hiroshi
-
依托单位:
国内基金
海外基金
登录
查看更多内容
XsmiR167为核心的ceRNA network调控文冠果雄花雌蕊败育机制研究
-
批准号:32572006
-
项目类别:面上项目
-
资助金额:50.00万元
-
批准年份:2025
-
负责人:敖妍
-
依托单位:
铜募集微纳米网片上调LOX活性稳定胶原网络促进盆底修复的研究
-
批准号:82371638
-
项目类别:面上项目
-
资助金额:49.00万元
-
批准年份:2023
-
负责人:陈信良
-
依托单位:
GPSM1介导Ca2+循环-II型肌球蛋白网络调控脂肪产热及代谢稳态的机制研究
-
批准号:82370879
-
项目类别:面上项目
-
资助金额:49.00万元
-
批准年份:2023
-
负责人:严婧
-
依托单位:
RagD调控mTORC2溶酶体定位的机制及功能研究
-
批准号:32100578
-
项目类别:青年科学基金项目(C类)
-
资助金额:30.0万元
-
批准年份:2021
-
负责人:陈蕾
-
依托单位:
机械力传导的分子机制—细胞感知力与诱导基因表达的方式如何?
-
批准号:32070777
-
项目类别:面上项目
-
资助金额:58.0万元
-
批准年份:2020
-
负责人:Fumihiko Nakamura
-
依托单位:
Notch1/β-catenin/Pax6通路调控角膜缘干细胞分化的机制研究
-
批准号:32000537
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2020
-
负责人:李根
-
依托单位:
丝氨酸/甘氨酸/一碳代谢网络(SGOC metabolic network)调控炎症性巨噬细胞活化及脓毒症病理发生的机制研究
-
批准号:81930042
-
项目类别:重点项目
-
资助金额:305.0万元
-
批准年份:2019
-
负责人:王迪
-
依托单位:
Jab1依赖结合蛋白和去泛素化功能在DNA损伤反应中的双重作用研究
-
批准号:31900558
-
项目类别:青年科学基金项目
-
资助金额:24.0万元
-
批准年份:2019
-
负责人:潘运宝
-
依托单位:
多维在线跨语言Calling Network建模及其在可信国家电子税务软件中的实证应用
-
批准号:91418205
-
项目类别:重大研究计划
-
资助金额:170.0万元
-
批准年份:2014
-
负责人:郑庆华
-
依托单位:
以PXR、CAR为核心的调控网络、作用机制及其指导环磷酰胺个体化用药的临床转化研究
-
批准号:81173131
-
项目类别:面上项目
-
资助金额:60.0万元
-
批准年份:2011
-
负责人:王雪丁
-
依托单位: