All reports by Author Udi Rotics:

__
TR05-081
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width II: non-approximability of clique-width

Revisions: 1

__
TR05-080
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

Revisions: 1

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter that measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic with second-order

quantification on vertex sets, that includes NP-hard problems) can be

solved efficiently for graphs of certified small clique-width. It is

widely ...
more >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter, defined by a composition mechanism

for vertex-labeled graphs, which measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic, that includes NP-hard

problems) can be solved efficiently for graphs of certified small

clique-width. It ...
more >>>