Alternative Proof of Linear Tangle and Linear Obstacle: An Equivalence Result
Asian Research Journal of Mathematics, Volume 19, Issue 8,
Page 61-66
DOI:
10.9734/arjom/2023/v19i8687
Abstract
Linear-width is a widely recognized and highly valued graph width parameter. The concepts of linear tangle and linear obstacle are dual concepts of linear-width. In this concise paper, we present an alternative proof of the equivalence between linear tangle and linear obstacle.
- Linear width
- linear tangle
- linear obstacle
- connectivity system
How to Cite
References
Yamazaki, Koichi. Tangle and maximal ideal." WALCOM: Algorithms and Computation: 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017, Proceedings 11. Springer International Publishing; 2017.
Fluck, E. Tangles and Hierarchical Clustering. arXiv preprint arXiv:2203.08731; 2022.
Fedor V Fomin, Dimitrios M Thilikos. On the monotonicity of games generated by symmetric submodular functions. Discrete Applied Mathematics. 2003;131(2):323–335.
Jim Geelen, Bert Gerards, Neil Robertson, Geoff Whittle. Obstructions to branch-decomposition of matroids. Journal of Combinatorial Theory, Series B. 2006;96(4):560–570.
Koutsonas, Athanassios, Dimitrios M. Thilikos, and Koichi Yamazaki. Outerplanar obstructions for matroid pathwidth. Discrete Mathematics. 2014;315:95-101.
Paul, Christophe, Evangelos Protopapas, Dimitrios M. Thilikos. Graph parameters, universal obstructions, and WQO. arXiv preprint arXiv:2304.03688; 2023.
Reed, Bruce A. Tree width and tangles: A new connectivity measure and some applications. Surveys in combinatorics. 1997;87-162.
Diestel Reinhard. Ends and tangles. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. BerlinHeidelberg: Springer Berlin Heidelberg. 2017;87(2).
Fujita T. Revisiting Linear Width: Rethinking the Relationship Between Single Ideal and Linear Obstacle. arXiv preprint arXiv:2305.04740; 2023.
Fomin, Fedor V, Tuukka Korhonen. Fast fpt-approximation of branchwidth. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing; 2022.
Kanté, Mamadou Moustapha, et al. Obstructions for matroids of path-width at most k and Graphs of linear rank-width at most k. Journal of Combinatorial Theory, Series B. 2023;160:15-35.
Kobayashi, Yasuaki, Yu Nakahata. A note on exponential-time algorithms for linearwidth. arXiv preprint arXiv:2010.02388; 2020.
Fujita T. Reconsideration of tangle and ultrafilter using separation and partition. arXiv preprint arXiv:2305.04306; 2023.
Bumpus Benjamin Merlin, Meeks Kitty, Pettersson William. Directed branch-width: A directed analogue of tree-width. arXiv preprint arXiv:2009.08903; 2020.
Bożyk Łukasz, et al. On objects dual to tree-cut decompositions. Journal of Combinatorial Theory, Series B. 2022;157:401-428.
Takaaki Fujita, Koichi Yamazaki. Linear-width and single ideal. The 20th Anniversary of the Japan Conference on Discrete and Computational Geometry, Graphs, and Games. 2017;110‒111.
Fujita T, Yamazaki K. Equivalence between Linear Tangle and Single Ideal. Open Journal of Discrete Mathematics. 2019;9:7-10.
DOI: 10.4236ojdm.2019.91002
Daniel Bienstock. Graph searching, path-width, tree-width and related problems (a survey). Reliability of Computer and Communication Networks , Vol.DIMACS. Series in Discrete Mathematics and Theoretical Computer Science. 1989;33‒50.
Fujita, Takaaki, and Koichi Yamazaki. Tangle and ultrafilter: Game theoretical interpretation. Graphs and Combinatorics. 2020;36(2):319-330.
Seymour P, Thomas R. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B. 1993;58(1):22–23.
Isolde Adler. Games for width parameters and monotonicity. arXiv preprint arXiv:0906.3857; 2009.
Schlechta, Karl. Non-monotonic logic: preferential versus algebraic semantics. David Makinson on Classical Methods for Non-Classical Problems. 2014;167-193.
Dov Gabbay, Karl Schlechta. Conditionals and modularity in general logics; 2010.
-
Abstract View: 15 times
PDF Download: 7 times