×

zbMATH — the first resource for mathematics

Characterizing graphs of maximum matching width at most 2. (English) Zbl 1395.05133
Summary: The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most \(2\) using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Arnborg, S.; Proskurowski, A.; Corneil, D. G., Forbidden minors characterization of partial 3-trees, Discrete Math., 80, 1, 1-19, (1990) · Zbl 0701.05016
[2] Bodlaender, H. L.; Kratsch, S.; Kreuzen, V. J.; Joung Kwon, O.; Ok, S., Characterizing width two for variants of treewidth, Discrete Appl. Math., 216, 1, 29-46, (2017) · Zbl 1350.05116
[3] Bodlaender, H. L.; Thilikos, D. M., Graphs with branchwidth at most three, J. Algorithms, 32, 2, 167-194, (1999) · Zbl 0946.68103
[4] Courcelle, B., The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Inform. and Comput., 85, 1, 12-75, (1990) · Zbl 0722.03008
[5] Dvořák, Z.; Giannopoulou, A. C.; Thilikos, D. M., Forbidden graphs for tree-depth, European J. Combin., 33, 5, 969-979, (2012), EuroComb ’09 · Zbl 1239.05062
[6] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combinatorial Theory Ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[7] Jelínek, V., The rank-width of the square grid, Discrete Appl. Math., 158, 7, 841-850, (2010) · Zbl 1219.05153
[8] Jeong, J.; Sther, S. H.; Telle, J. A., Maximum matching width: new characterizations and a fast algorithm for dominating set, (Husfeldt, T.; Kanj, I., 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Leibniz International Proceedings in Informatics (LIPIcs), vol. 43, (2015), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany), 212-223 · Zbl 1378.68082
[9] Kinnersley, N. G.; Langston, M. A., Obstruction set isolation for the gate matrix layout problem, Discrete Appl. Math., 54, 2, 169-213, (1994) · Zbl 0941.68590
[10] Lokshtanov, D.; Marx, D.; Saurabh, S., Known algorithms on graphs of bounded treewidth are probably optimal, (Proceedings of the Twenty-SEcond Annual ACM-SIAM Symposium on Discrete Algorithms, (2011), SIAM Philadelphia, PA), 777-789 · Zbl 1373.68242
[11] Read, R.; Wilson, R., (An Atlas of Graphs, (1998), Oxford Science Publications, Clarendon Press) · Zbl 0908.05001
[12] Robertson, N.; Seymour, P., Graph minors. X. obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 2, 153-190, (1991) · Zbl 0764.05069
[13] Robertson, N.; Seymour, P., Graph minors. XX. wagner’s conjecture, J. Combin. Theory Ser. B, 92, 2, 325-357, (2004), Special Issue Dedicated to Professor W.T. Tutte · Zbl 1061.05088
[14] S.H. Sæther, J.A. Telle, Personal communication.
[15] Sæther, S. H.; Telle, J. A., Between treewidth and clique-width, Algorithmica, 75, 1, 218-253, (2016) · Zbl 1345.05104
[16] Satyanarayana, A.; Tung, L., A characterization of partial 3-trees, Networks, 20, 3, 299-322, (1990) · Zbl 0701.90092
[17] Seymour, P.; Thomas, R., Graph searching and a MIN-MAX theorem for tree-width, J. Combin. Theory Ser. B, 58, 1, 22-33, (1993) · Zbl 0795.05110
[18] Tutte, W., A theory of 3-connected graphs, Indag. Math., 64, 441-455, (1961) · Zbl 0101.40903
[19] van Rooij, J. M.M.; Bodlaender, H. L.; Rossmanith, P., Dynamic programming on tree decompositions using generalised fast subset convolution, (Algorithms—ESA 2009, Lecture Notes in Comput. Sci., vol. 5757, (2009), Springer Berlin), 566-577 · Zbl 1256.68157
[20] Vatshelle, M., New Width Parameters of Graphs (Ph.D. thesis), (2012), University of Bergen
[21] Wald, J. A.; Colbourn, C. J., Steiner trees, partial \(2\)-trees, and minimum IFI networks, Networks, 13, 2, 159-167, (1983) · Zbl 0529.68036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.