Stable sets and special graph classes.
稳定集和特殊图类。
基本信息
- 批准号:5299366
- 负责人:
- 金额:--
- 依托单位:
- 依托单位国家:德国
- 项目类别:Research Units
- 财政年份:2001
- 资助国家:德国
- 起止时间:2000-12-31 至 2009-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Stabile Mengen in Graphen bilden eines der wichtigen Modelle in der ganzzahligen Optimierung. Anwendung finden stabile Mengen z.B. bei der ÖPNV-Dienstplanung, beim Airline Crew-Scheduling und gewissen Fahrzeugeinsatzplanungen. Das Stabile-MengenProblem ist jedoch i.A. NP-schwer. Die polynomiale Lösbarkeit des Stabile-Mengen-Problems ist nur für wenige Graphenklassen bekannt. Unter diesen sind perfekte Graphen die strukturell interessantesten: Charakterisierungen perfekter Graphen bilden eine Schnittstelle zwischen Graphentheorie, Polyedertheorie, Informationstheorie sowie ganzzahliger Programmierung und liefern Einblicke in Zusammenhänge dieser Gebiete. Der Schwerpunkt dieses Projektes liegt auf zwei Verallgemeinerungen des Perfektheitsbegriffes: hinsichtlich der polyedertheoretischen und hinsichtlich der informationstheoretischen Charakterisierung perfekter Graphen. Ein Gegenstand der Untersuchung sind strukturelle Eigenschaften und Stabile-Mengen-Polytope von Klassen "fast" perfekter Graphen und von Oberklassen perfekter Graphen im polyedertheoretischen Sinne. Dadurch soll, wenn möglich, die Zahl der Graphenklassen erhöht werden, für die polynomiale Lösbarkeit des Stabile-Mengen-Problems bewiesen werden kann. In Zusammenarbeit mit der Arbeitsgruppe Ziegler ist weiter das Studium der Struktur von 0/1-Polytopen am Beispiel von StabileMengen-Polytopen geplant. Eine informationstheoretische Oberklasse perfekter Graphen bilden die normalen Graphen, basierend auf schwacher Additivität der Graph-Entropie. Wie sich diese Erweiterung des Perfektheitsbegriffes graphen- bzw. polyedertheoretisch auswirkt und welche Bedeutung dabei den Wahrscheinlichkeitsverteilungen zukommt, ist Gegenstand der Zusammenarbeit mit der Arbeitsgruppe Prömel.
稳定的Mengen在Graphen bilden一个wichtigen模型在der ganzzahligen优化。Anwendung finden stabile Mengen z.B. bei der ÖPNV-Dienstplanung,beim Airline Crew-Scheduling und gewissen Fahrzeugeinsatzplanungen.稳定性问题是一个很小的问题。NP-schwer。Die polynomiale Lösbarkeit des Stabile-Mengen-Problems ist努尔für wenige Graphenklassen bekannt.在这种情况下,Graphen的结构是完美的:它的特性使Graphen产生了一种新的图形理论、聚合物理论、信息理论,这些理论都是可编程的,并且在这方面有着很大的优势。Schwerpunkt的这个项目包含两种不同的PerfektheitsBegriffes:混合理论和信息理论的特性。一个研究的基础是在多理论中对Klassen“fast”perfekter Graphen和Oberklassen perfekter Graphen的特征结构和稳定-Mengen-Polytope。Dadesol,wenn möglich,die Zahl der Graphenklassen erhöht韦尔登,for die polynomiale Lösbarkeit des Stabile-Mengen-Problems bewiesen韦尔登.在齐格勒工作组的协作下,我们对0/1-多面体的结构和稳定多面体的结构进行了研究。一种基于图熵的schwacher可加性的信息理论优化Graphen生成标准Graphen。这是一个完美的图形化的过程.这是与劳动者群体合作的一种形式。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Professor Dr. Martin Grötschel其他文献
Professor Dr. Martin Grötschel的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Professor Dr. Martin Grötschel', 18)}}的其他基金
Digitizing of Jean Paul's complete letters from the critical edition
将批评版中的让·保罗完整信件数字化
- 批准号:
282799084 - 财政年份:2016
- 资助金额:
-- - 项目类别:
Cataloguing and Digitisation (Scientific Library Services and Information Systems)
Multi-criteria optimization models for the deployment of FTTx networks, development and implementation of algorithmic approaches
用于 FTTx 网络部署、算法方法开发和实施的多标准优化模型
- 批准号:
211347751 - 财政年份:2012
- 资助金额:
-- - 项目类别:
Research Grants
Optimization models and methods for telecommunication network design with varying and uncertain demands
具有变化和不确定需求的电信网络设计的优化模型和方法
- 批准号:
157172886 - 财政年份:2009
- 资助金额:
-- - 项目类别:
Research Grants
Echtzeit-Optimierung komplexer Transportsysteme
复杂运输系统的实时优化
- 批准号:
5251344 - 财政年份:1995
- 资助金额:
-- - 项目类别:
Priority Programmes
相似国自然基金
基于Fuzzy Sets的视频差错掩盖技术研究
- 批准号:60672134
- 批准年份:2006
- 资助金额:25.0 万元
- 项目类别:面上项目
浅电子陷阱掺杂剂对光电子衰减过程的影响
- 批准号:10354001
- 批准年份:2003
- 资助金额:15.0 万元
- 项目类别:专项基金项目
相似海外基金
Spatial restriction of exponential sums to thin sets and beyond
指数和对稀疏集及以上的空间限制
- 批准号:
2349828 - 财政年份:2024
- 资助金额:
-- - 项目类别:
Standard Grant
Research Initiation Award: Turan-type problems on partially ordered sets
研究启动奖:偏序集上的图兰型问题
- 批准号:
2247163 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Standard Grant
Advances on Combinatorics of the Real Line and Topology
实线与拓扑组合学研究进展
- 批准号:
23K03198 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Scientific Research (C)
New approaches for leveraging single-cell data to identify disease-critical genes and gene sets
利用单细胞数据识别疾病关键基因和基因集的新方法
- 批准号:
10768004 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Collaborative Research: Data-Driven Invariant Sets for Provably Safe Autonomy
协作研究:数据驱动的不变集可证明安全的自治
- 批准号:
2303157 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Standard Grant
LEAPS-MPS: Controllable sets for nonlinear switched models with applications to infectious diseases
LEAPS-MPS:非线性切换模型的可控集及其在传染病中的应用
- 批准号:
2315862 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Standard Grant
On a Combinatorial Characterization of Dynamical Invariant Sets of Regulatory Networks
关于调节网络动态不变集的组合表征
- 批准号:
23K03240 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Scientific Research (C)
Constructing large scale data sets, developing methods to analyze such data sets, and their empirical implementations
构建大规模数据集,开发分析此类数据集的方法及其实证实施
- 批准号:
23K17285 - 财政年份:2023
- 资助金额:
-- - 项目类别:
Grant-in-Aid for Challenging Research (Pioneering)