Volume 12 • Issue 1 • PP: 24-35 • 2025
Linear-Branch-Decomposition of Digraph
Open Access & Copyright
© 2025 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
View PDF Abstract
The study of graph width parameters is a well-established field within graph theory. Recently, numerous researchers have been actively extending undirected width parameters to directed graphs, resulting in a wide range of studies on directed width parameters. In this paper, we introduce a new concept called Directed Linear-Branch-Width, which extends the (Undirected) Linear-Branch-Width to digraphs. We also investigate its relationship and hierarchy with Directed Path-width, Directed Cut-width, and Directed Neighbourhood- width
Keywords
References
[1] Isolde Adler. Directed tree-width examples. Journal of Combinatorial Theory, Series B, 97(5):718–725, 2007.
[2] Isolde Adler and Mamadou Moustapha Kant´e. Linear rank-width and linear clique-width of trees. Theoretical Computer Science, 589:87–98, 2015.
[3] Jørgen Bang-Jensen and Gregory Z Gutin. Digraphs: theory, algorithms and applications. Springer Science & Business Media, 2008.
[4] J´anos Bar´at. Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics, 22(2):161–172, 2006.
[5] Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, and Jan Obdrˇz´alek. The dag-width of directed graphs. Journal of Combinatorial Theory, Series B, 102(4):900–923, 2012.
[6] Benjamin Merlin Bumpus, Kitty Meeks, and William Pettersson. Directed branch-width: A directed analogue of tree-width. arXiv preprint arXiv:2009.08903, 2020.
[7] Fedor V Fomin and Dimitrios M Thilikos. On the monotonicity of games generated by symmetric submodular functions. Discrete Applied Mathematics, 131(2):323–335, 2003.
[8] Takaaki Fujita. Matroid, ideal, ultrafilter, tangle, and so on: Reconsideration of obstruction to linear decomposition. International Journal of Mathematics Trends and Technology (IJMTT), 70:18–29, 2024.
[9] Frank Gurski, Dominique Komander, and Carolin Rehs. Acyclic coloring parameterized by directed clique-width. In Conference on Algorithms and Discrete Applied Mathematics, pages 95–108. Springer, 2021.
[10] Frank Gurski, Dominique Komander, Carolin Rehs, and Sebastian Wiederrecht. Directed width parameters on semicomplete di-graphs. In Combinatorial Optimization and Applications: 15th International Conference, COCOA 2021, Tianjin, China, December 17–19, 2021, Proceedings 15, pages 615–628. Springer, 2021.
[11] Frank Gurski and Carolin Rehs. Comparing linear width parameters for directed graphs. Theory of Computing Systems, 63:1358–1387, 2019.
[12] Frank Gurski, Carolin Rehs, and Jochen Rethmann. Directed path-width of sequence digraphs. In International Conference on Combinatorial Optimization and Applications, pages 79–93. Springer, 2018.
[13] Frank Gurski, Egon Wanke, and Eda Yilmaz. Directed nlc-width. Theoretical Computer Science, 616:1–17, 2016.
[14] Pinar Heggernes, Daniel Meister, and Charis Papadopoulos. Graphs of linear clique-width at most 3. Theoretical Computer Science, 412(39):5466–5486, 2011.
[15] Paul Hunter and Stephan Kreutzer. Digraph measures: Kelly decompositions, games, and orderings. Theoretical Computer Science, 399(3):206–219, 2008.
[16] Thor Johnson, Neil Robertson, Paul D Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138–154, 2001.
[17] Mamadou Moustapha Kant´e and Micha¨el Rao. Directed rank-width and displit decomposition. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 214–225. Springer, 2009.
[18] Shoji Kasahara, Jun Kawahara, Shin-ichi Minato, and Jumpei Mori. Dag-pathwidth: graph algorithmic analyses of dag-type blockchain networks. IEICE TRANSACTIONS on Information and Systems, 106(3):272–283, 2023.
[19] Shiva Kintali, Nishad Kothari, and Akash Kumar. Approximation algorithms for digraph width parameters. Theoretical Computer Science, 562:365–376, 2015.
[20] Sang-il Oum. Rank-width: Algorithmic and structural results. Discrete Applied Mathematics, 231:15–24, 2017.
[21] Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39–61, 1983.
[22] Neil Robertson and Paul D. Seymour. Graph minors. x. obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991.
[23] Mohammad Ali Safari. D-width: A more natural measure for directed tree width. In Mathematical Foundations of Computer Science 2005: 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29–September 2, 2005. Proceedings 30, pages 745–756. Springer, 2005.
[24] Robert Sasak. Comparing 17 graph parameters. Master’s thesis, The University of Bergen, 2010.
[25] Raphael Steiner and Sebastian Wiederrecht. Parameterized algorithms for directed modular width. In Conference on Algorithms and Discrete Applied Mathematics, pages 415–426. Springer, 2020.
[26] Dimitrios M Thilikos. Algorithms and obstructions for linear-width and related search parameters. Discrete Applied Mathematics, 105(1-3):239–271, 2000.
[27] Robin Thomas. Tree-decompositions of graphs (lecture notes). School of Mathematics. Georgia Institute of Technology, Atlanta, Georgia, 30332, 1996.
[28] Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
Cite This Article
Choose your preferred format
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.