-2
$\begingroup$

in the following paper http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/full the author describes the minimax problem as follows:

Given a graph G = (V, E), we are looking for a particular coloring $C \subseteq E$ such that no two edges in $C$ share a vertex and -- and this is the part I'm confused about -- if nodes $u$ and $v$ belong to edges in $C$ then the edge (u, v) isn't in $E$.

But that clearly can't make sense because somehow that means that if $(u, v) \in C$ then $(u, v) \not\in E$ but $C \subseteq E$.

Would the correct form of the second requirement be that: For each $(u, v) \in E - C$ there exists an edge in $C$ that is adjacent to either $u$ or $v$?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

I gave a quick look, it looks like you didn't copy the definition right, the second requirement state that if $u$ e $v$ belong to $D$, not $C$, then $(u,v) \notin E$, where $D = \bigcup_{e \in C}∂e$. What I guess they mean is that if, say, $(a,b)$ and $(c,d)$ belong to $C$ and $(u,a)$, $(c,v)$ belong to $E$ then $(u,v) \notin E$ otherwise it could be added to $C$ and it would still be a valid matching.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Just to clarify, for an edge $e = (u,v)$ does $\partial e$ denote the set $\{u, v\}$? $\endgroup$
    – Lagerbaer
    Jul 7, 2015 at 16:29
  • $\begingroup$ I don't think so. From earlier in the paper, "$∂v$ corresponds to the subset of $E$ of edges which connect to $v$". On edges, the meaning of ∂ doesn't seem to be formally defined, hence I am assuming it is what seems to me to be the natural extension: for an edge $e=(u,v)$, I think $∂e$ represents the subset of edges of $E$ with an endpoint equal to either $u$ or $v$. $\endgroup$
    – drew
    Jul 7, 2015 at 18:35
0
$\begingroup$

The standard definition of the minimum maximal matching problem is exactly what it sounds like: we are looking for a matching (a set $C$ of edges, no two of which share an endpoint) which is maximal (if $e \not \in C$, then $C \cup \{e\}$ is not a matching) with the smallest possible size (i.e. we wish to minimize $|C|$, over all maximal matchings $C$.)

I'm not sure how to interpret the definition in the paper to which you linked. If you replace the second requirement with your proposed criterion, you end up with a definition of a maximal matching.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.