Computing the clique-width of cactus graphs

DOI10.1016/J.ENTCS.2016.11.005MaRDI QIDQ1744436zbMATH OpenOpenAlexWikidataFDO

Authors J. Leonardo González-Ruiz, J. Raymundo Marcial-Romero, J. A. Hernández-Servín

Publication date 23 April 2018

Full work available at URL https://doi.org/10.1016/j.entcs.2016.11.005

zbMATH Keywords

clique-widthcomplexitytree-width

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Approximating clique-width and branch-width
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• The relative clique-width of a graph
• Upper bounds to the clique width of graphs
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Clique-width for graph classes closed under complementation
• scientific article; zbMATH DE number 7204407
• Deciding clique-width for graphs of bounded tree-width (extended abstract)
• Bounding clique-width via perfect graphs
• Bounding clique-width via perfect graphs

Cites work

• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Approximating clique-width and branch-width
• Centdian Computation for Sensor Networks
• Graph classes with and without powers of bounded clique-width
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 6691415 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• Intractability of clique-width parameterizations
• Line graphs of bounded clique-width
• On the clique-width of perfect graph classes (extended abstract)
• On the relationship between clique-width and treewidth
• Polynomial-time recognition of clique-width 3 graphs
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• The tree-width of clique-width bounded graphs without \(K_{n,n}\)
• Upper bounds to the clique width of graphs

Cited in

(1)

• Inductive computations on graphs defined by clique-width expressions

This page was built for publication: Computing the clique-width of cactus graphs

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