On the thinness of trees

DOI10.1007/978-3-031-18530-4_14zbMath1528.90205OpenAlexW4312742781MaRDI QIDQ6166903

Flavia Bonomo-Braberman, Eric Brandwein, Agustín Sansone, Carolina Lucía Gonzalez

Publication date: 3 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-18530-4_14

zbMATH Keywords

polynomial time algorithmtreesthinness

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Solving problems on generalized convex graphs via mim-width
• The complexity of comparability graph recognition and coloring
• The vertex separation and search number of a graph
• Column subset selection is NP-complete
• Linear MIM-width of trees
• On the thinness and proper thinness of a graph
• The stable set problem and the thinness of a graph
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Twin-width I: Tractable FO Model Checking
• Parameterized Algorithms
• Twin-width and transductions of proper \(k\)-mixed-thin graphs

This page was built for publication: On the thinness of trees