ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Perfectness is an Elusive Graph Property (2002)

Hougardy, Stefan ; Wagler, Annegret

add to mindlist on the mindlist

Details

Publication Date: 2014-02-26

Description: A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.

Keywords: ddc:000

Language: English

Type: reportzib , doc-type:preprint

Format: application/postscript

Format: application/pdf

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview

hit 1 - 1 | 1 hit