Inductive computations on graphs defined by clique-width expressions

DOI10.1051/ita/2009010zbMath1176.68139OpenAlexW2102165439MaRDI QIDQ5321781

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/

zbMATH Keywords

graphsclique-widthlabeling schemestermsinductive computation

Mathematics Subject Classification ID

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

Cites Work

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

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