Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MICHAEL R. FELLOWS:
All reports by Author Michael R. Fellows:

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

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 >>>


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

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 >>>




ISSN 1433-8092 | Imprint