Publication | Open Access
Deciding Clique-Width for Graphs of Bounded Tree-Width
42
Citations
0
References
2003
Year
Mathematical ProgrammingEngineeringPlanar GraphNetwork AnalysisEducationComputational ComplexityLinear Time AlgorithmStructural Graph TheoryDiscrete MathematicsCombinatorial OptimizationClique-width KBounded Tree-widthComputer ScienceGraph AlgorithmGraph MinorNetwork ScienceGraph TheoryFixed Integer KExtremal Graph Theory
We show that there exists a linear time algorithm for deciding whether a graph of bounded tree-width has clique-width k for some fixed integer k.