Cutwidth of the de Bruijn graph
André Raspaud, Ondrej Sýkora, Imrich Vrt'o (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Displaying similar documents to “Pebbling dynamic graphs in minimal space”
Cutwidth of the de Bruijn graph
Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete.
Abbas, N., Culberson, J., Stewart, L. (2005)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
A survey of the algorithmic properties of simplicial, upper bound and middle graphs.
Cheston, Grant A., Jap, Tjoen Seng (2006)
Journal of Graph Algorithms and Applications
Similarity:
Note: The Smallest Nonevasive Graph Property
Michał Adamaszek (2014)
Discussiones Mathematicae Graph Theory
Similarity:
A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs...
Some constructions of -minimal graphs
Francesco Regonati, N. Zagaglia Salvi (1994)
Czechoslovak Mathematical Journal
Similarity:
On bandwidth, cutwidth, and quotient graphs
Dominique Barth, François Pellegrini, André Raspaud, Jean Roman (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity: