论文标题
部分可观测时空混沌系统的无模型预测
Partial and Simultaneous Transitive Orientations via Modular Decomposition
论文作者
论文摘要
几何图类别的识别问题的自然概括是将子图表的表示形式扩展到整个图的表示。一个相关的问题是找到对输入图共享子图的多个输入图的表示形式。一个常见的限制是向日葵案例，每对输入图的共享图相同。这些问题转化为可比较图的设置，其中表示对应于其边缘的传递方向。我们使用模块化分解来改善方向扩展问题的运行时以及向日葵方向问题到线性时间。我们应用这些结果来改善部分表示问题的运行时间和同时表示图表的同时表示形式的葵花籽情况。我们还为这些问题提供了第一个有效的算法，这些算法在圆形排列图上。
A natural generalization of the recognition problem for a geometric graph class is the problem of extending a representation of a subgraph to a representation of the whole graph. A related problem is to find representations for multiple input graphs that coincide on subgraphs shared by the input graphs. A common restriction is the sunflower case where the shared graph is the same for each pair of input graphs. These problems translate to the setting of comparability graphs where the representations correspond to transitive orientations of their edges. We use modular decompositions to improve the runtime for the orientation extension problem and the sunflower orientation problem to linear time. We apply these results to improve the runtime for the partial representation problem and the sunflower case of the simultaneous representation problem for permutation graphs to linear time. We also give the first efficient algorithms for these problems on circular permutation graphs.
