التفاصيل البيبلوغرافية
| العنوان: |
Vertex-Bipartition: A Unified Approach for Kernelization of Graph Linear Layout Problems Parameterized by Vertex Cover. |
| المؤلفون: |
Liu, Yunlong, Li, Yixuan, Huang, Jingui |
| المصدر: |
International Journal of Foundations of Computer Science; Sep2024, Vol. 35 Issue 6, p609-629, 21p |
| مصطلحات موضوعية: |
GRAPH algorithms, INTEGERS, ALGORITHMS, LINEAR orderings |
| مستخلص: |
The Linear Layout of Graphs problem asks, given a graph G and a positive integer k , whether G admits a layout consisting of a linear ordering of its vertices and a partition of its edges into k sets such that the edges in each set meet some special requirements. Specific linear layouts include k -Stack Layout, k -Queue Layout, k -Arch Layout, Mixed s -Stack q -Queue Layout and others. In this paper, we present a unified approach for kernelization of these linear layout problems parameterized by the vertex cover number τ of the input graph. The key point underlying our approach is to partition each set of related vertices into two distinct subsets with respect to the specific layouts, which immediately leads to some efficient reduction rules. We first apply this approach to the Mixed s -Stack q -Queue Layout problem and show that it admits a kernel of size 2 (τ) , which results in an algorithm running in time (2 2 (τ) + τ ⋅ | V |) , where | V | denotes the size of the input graph. Our work does not only confirm the existence of a fixed-parameter tractable algorithm for this problem mentioned by Bhore et al. (J. Graph Algorithms Appl. 2022), but also derives new results for the k -Stack Layout problem and for the k -Queue Layout problem respectively. We also employ this approach to the Upward k -Stack Layout problem and obtain a new result improving that presented by Bhore et al. (GD 2021). Last but not least, we use this approach to the k -Arch Layout problem and obtain a similar result. [ABSTRACT FROM AUTHOR] |
|
Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
