Induced tree covering and the generalized Yutsis property

DOI10.1007/978-3-031-55601-2_10MaRDI QIDQ6547951zbMATH OpenFDO

Authors Luís Felipe Ignácio Cunha, Gabriel L. Duarte, Fábio Protti, Loana T. Nogueira, Uéverton S. Souza

Publication date 31 May 2024

Full work available at URL https://doi.org/10.1007/978-3-031-55601-2_10

zbMATH Keywords

clique-widthinduced tree coversplit graphstreewidthYutsis graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• Graph structural properties of non-Yutsis graphs allowing fast recognition
• On the tree cover number of a graph
• To be or not to be Yutsis: algorithms for the decision problem
• Maximum induced trees in graphs

Cites work

• Approximating clique-width and branch-width
• Complexity of the hamiltonian cycle in regular graph problem
• Computing the largest bond and the maximum connected cut of a graph
• Computing the largest bond of a graph
• Connecting constructive notions of ordinals in homotopy type theory
• Euler and bipartite matroids
• Graph structural properties of non-Yutsis graphs allowing fast recognition
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3180958 (Why is no real title available?)
• scientific article; zbMATH DE number 3743204 (Why is no real title available?)
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• Improved approximation algorithms for the MIN-MAX tree cover and bounded tree cover problems
• Intractability of clique-width parameterizations
• Known algorithms on graphs of bounded treewidth are probably optimal
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimum semidefinite rank of outerplanar graphs and the tree cover number
• Note on positive semidefinite maximum nullity and positive semidefinite zero forcing number of partial 2-trees
• On the minimum cycle cover problem on graphs with bounded co-degeneracy
• On the reduction of Yutsis graphs
• On the tree cover number of a graph
• Parameterized algorithms
• Slightly superexponential parameterized problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Upper bounds to the clique width of graphs

Cited in

(1)

• Induced tree covering and the generalized Yutsis property

This page was built for publication: Induced tree covering and the generalized Yutsis property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6547951)