article · 2016

Decomposition-width: Extending the Clique-width to Hypergraphs

Yann Strozecki

Cited by 0Abstract and details only

Abstract

We define a width parameter for hypergraphs, which we call the decomposition-width. We provide an explicit family of hypergraphs of large decomposition-width and we prove that every MSO property can be checked in linear time for hypergraphs with bounded decomposition-width when their decomposition is given. Finally, the decomposition-width of a graph is proved to be bounded by twice its clique-width, which suggests that decomposition-width is a generalization of clique-width to relations of large or unbounded arity.

Cite this paper

APA 7

Strozecki, Y. (2016). Decomposition-width: Extending the Clique-width to Hypergraphs.

MLA 9

Strozecki, Yann. “Decomposition-width: Extending the Clique-width to Hypergraphs.” 2016.

Chicago

Strozecki, Yann. 2016. “Decomposition-width: Extending the Clique-width to Hypergraphs.”

Harvard

Strozecki, Y. (2016) ‘Decomposition-width: Extending the Clique-width to Hypergraphs’.

BibTeX

@article{strozecki2016decomposition,
  title = {{Decomposition-width: Extending the Clique-width to Hypergraphs}},
  author = {Strozecki, Yann},
  year = {2016}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.