|
| | | | |
| | | |
| Stat |
Members: 3647
Articles: 2'513'570
Articles rated: 2609
08 May 2024 |
|
| | | | |
|
Article overview
| |
|
|
Max Point-Tolerance Graphs | | Daniele Catanzaro
; Steven Chaplick
; Stefan Felsner
; Bjarni V. Halldórsson
; Magnús M. Halldórsson
; Thomas Hixon
; Juraj Stacho
; | | Date: |
16 Aug 2015 | | Abstract: | A graph $G$ is a emph{max point-tolerance (MPT)} graph if each vertex $v$ of
$G$ can be mapped to a emph{pointed-interval} $(I_v, p_v)$ where $I_v$ is an
interval of $mathbb{R}$ and $p_v in I_v$ such that $uv$ is an edge of $G$ iff
$I_u cap I_v supseteq {p_u, p_v}$. MPT graphs model relationships among DNA
fragments in genome-wide association studies as well as basic transmission
problems in telecommunications. We formally introduce this graph class,
characterize it, study combinatorial optimization problems on it, and relate it
to several well known graph classes. We characterize MPT graphs as a special
case of several 2D geometric intersection graphs; namely, triangle, rectangle,
L-shape, and line segment intersection graphs. We further characterize MPT as
having certain linear orders on their vertex set. Our last characterization is
that MPT graphs are precisely obtained by intersecting special pairs of
interval graphs. We also show that, on MPT graphs, the maximum weight
independent set problem can be solved in polynomial time, the coloring problem
is NP-complete, and the clique cover problem has a 2-approximation. Finally, we
demonstrate several connections to known graph classes; e.g., MPT graphs
strictly contain interval graphs and outerplanar graphs, but are incomparable
to permutation, chordal, and planar graphs. | | Source: | arXiv, 1508.3810 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
REGISTER