Research ArticleOpen AccessGoogle Scholar indexed
Equivalence between Linear Tangle and Maximal Single Ideal
Graduate School of Science and Technology, Gunma University, Gunma, Japan
Division of Electronics and Informatics, Gunma University, Gunma, Japan
- 1 Graduate School of Science and Technology, Gunma University, Gunma, Japan
- 2 Division of Electronics and Informatics, Gunma University, Gunma, Japan
Open Journal of Discrete Mathematics·Volume 09 (2018)·Pages 7–10·Published 17 December 2018·DOI10.4236/ojdm.2019.91002
Copy link · social · email
Abstract
The concept of linear tangle was introduced as an obstruction to mixed searching number. The concept of single ideal has been introduced as an obstruction to linear-width. Moreover, it was already known that mixed search number is equivalent to linear-width. Hence, by combining those results, we obtain a proof of the equivalence between linear tangle and single ideal. This short report gives an alternative proof of the equivalence.
KeywordsLinear TangleMaximal Single IdealSubmodular Function
- Aigner, M. and Fromme, M. (1984) A Game of Cops and Robbers. Discrete Applied Mathematics, 8, 1-12. https://doi.org/10.1016/0166-218X(84)90073-8
- Bonato, A. (2011) The Game of Cops and Robbers on Graphs. Vo. 12, The Student Mathematical Library. https://doi.org/10.1090/stml/061
- Bonato, A. and Yang, B.T. (2013) Graph Searching and Related Problems. In: Pardalos, P., Du, D.Z. and Graham, R., Eds., Handbook of Combinatorial Optimization, Springer, Berlin, 1511-1558. https://doi.org/10.1007/978-1-4419-7997-1_76
- Angelopoulos, S., Fraignaud, P., Fomin, F., Nisse, N. and Thilikos, D.M. (2017) Report on GRASTA 2017, 6th Workshop on Graph Searching, Theory and Applications, Anogia, Crete, Greece, April 10-13, 2017. https://hal-lirmm.ccsd.cnrs.fr/lirmm-01645614
- Fomin, F.V. and Thilikos, D.M. (2008) An Annotated Bibliography on Guaranteed Graph Searching. Theoretical Computer Science, 399, 236-245. https://doi.org/10.1016/j.tcs.2008.02.040
- Thilikos, D.M. (2000) Algorithms and Obstructions for Linear-Width and Related Search Parameters. Discrete Applied Mathematics, 105, 239-271. https://doi.org/10.1016/S0166-218X(00)00175-X
- Bienstock, D. (1989) Graph Searching, Path-Width, Tree-Width and Related Problems (a Survey). In Reliability of Computer and Communication Networks, Vol. 5 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 33-50.
- Fomin, F.V. and Thilikos, D.M. (2003) On the Monotonicity of Games Generated by Symmetric Submodular Functions. Discrete Applied Mathematics, 131, 323-335. https://doi.org/10.1016/S0166-218X(02)00459-6
- Fujita, T. and Yamazaki, K. (2017) Linear-Width and Single Ideal. The 20th Anniversary of the Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo University of Science, 29th August-1st September 2017, 110-111. http://www.jcdcgg.u-tokai.ac.jp/JCDCG3_2017_abstracts.pdf
- Geelen, J., Gerards, B., Robertson, N. and Whittle, G. (2006) Obstructions to Branch-Decomposition of Matroids. Journal of Combinatorial Theory, Series B, 96, 560-570. https://doi.org/10.1016/j.jctb.2005.11.001