Inductive computations on graphs defined by clique-width expressions

DOI10.1051/ITA/2009010MaRDI QIDQ5321781zbMATH OpenOpenAlexFDO

Authors F. Carrere

Publication date 15 July 2009

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2009__43_3_625_0/, https://eudml.org/doc/92930

zbMATH Keywords

clique-widthgraphsinductive computationlabeling schemesterms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Recommendations

• Computing the clique-width of cactus graphs
• Inductive graph invariants and approximation algorithms
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Inductive graph invariants and algorithmic applications
• scientific article; zbMATH DE number 1830724
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• From tree-decompositions to clique-width terms
• Clique-width and directed width measures for answer-set programming
• Approximating clique-width and branch-width
• scientific article; zbMATH DE number 7204407

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• A new approach to dynamic all pairs shortest paths
• Clique-width minimization is NP-hard
• Clique-width of countable graphs: A compactness property.
• Compact Forbidden-Set Routing
• Distance labeling in graphs
• Distance labeling scheme and split decomposition
• Easy problems for tree-decomposable graphs
• Efficient graph representations
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding Branch-Decompositions and Rank-Decompositions
• scientific article; zbMATH DE number 475414 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 1875437 (Why is no real title available?)
• LATIN 2004: Theoretical Informatics
• Monadic second-order evaluations on tree-decomposable graphs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Parametrized complexity theory.
• Query efficient implementation of graphs of bounded clique-width
• The complexity of first-order and monadic second-order logic revisited
• Upper bounds to the clique width of graphs

Cited in

(3)

• Optimal centrality computations within bounded clique-width graphs
• Clique-width with an inactive label
• Optimal centrality computations within bounded clique-width graphs

This page was built for publication: Inductive computations on graphs defined by clique-width expressions

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