The complexity of the independence and matching clutter of a graph

Details The complexity of the independence and matching clutter of a graph The complexity of the independence and matching clutter of a graph

2009-03-28

arxiv.org/abs/0903.4907v3

Computer Science

Discrete Mathematics

23 pages, 5 figures

Scientific paper

A clutter $L$ is a pair $(V,E)$, where $V$ is a finite set and $E$ is a family of subsets of $V$ none of which is a subset of another. Usually, the elements of $V$ are called vertices of $L$, and the elements of $E$ are called edges of $L$. A subset $s_e$ of an edge $e$ of a clutter is called recognizing for $e$, if $s_e$ is not a subset of another edge. The complexity of an edge $e$ of a clutter is the ratio of the size of $e\textrm{'s}$ smallest recognizing subset to the size of $e$. The complexity of a clutter is the maximum of the complexities of its edges. We study the complexity of clutters arising from independent sets and matchings of graphs.

Affiliated with

Also associated with

No associations

Rating

The complexity of the independence and matching clutter of a graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The complexity of the independence and matching clutter of a graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of the independence and matching clutter of a graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-187987