From Tree-Width to Clique-Width: Excluding a Unit Interval Graph

DOI10.1007/978-3-540-92182-0_76MaRDI QIDQ3597886zbMATH OpenOpenAlexFDO

Authors Vadim Lozin

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_76

zbMATH Keywords

clique-widthfixed parameter tractabilitytree-widthunit interval graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1439435
• Critical properties of graphs of bounded clique-width
• scientific article; zbMATH DE number 1420904
• Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
• Infinitely many minimal classes of graphs of unbounded clique-width

Cited in

(7)

• Computing the clique-width of large path powers in linear time via a new characterisation of clique-width
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• scientific article; zbMATH DE number 1439435 (Why is no real title available?)
• On the clique-width of some perfect graph classes
• Compact labelings for efficient first-order model-checking
• On first-order transductions of classes of graphs

This page was built for publication: From Tree-Width to Clique-Width: Excluding a Unit Interval Graph

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