Volume 12 • Issue 1 • PP: 24-35 • 2025
Linear-Branch-Decomposition of Digraph
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