On the thinness of trees

DOI10.1007/978-3-031-18530-4_14MaRDI QIDQ6166903zbMATH OpenOpenAlexFDO

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

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

treespolynomial time algorithmthinness

Mathematics Subject Classification ID

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

Recommendations

• On the thinness and proper thinness of a graph
• Thinness of product graphs
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Thinness and its variations on some graph families and coloring graphs of bounded thinness

Cites work

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

Cited in

(5)

• scientific article; zbMATH DE number 5054164 (Why is no real title available?)
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• On the strength of some trees
• scientific article; zbMATH DE number 3957503 (Why is no real title available?)
• Thinness and its variations on some graph families and coloring graphs of bounded thinness

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

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