[
{
    "url": "https://wou.omeka.net/s/repository/item/1168",
    "dcterms:title": [
        "Recognition Algorithm for Probe Interval 2-Trees"
    ],
    "dcterms:creator": [
        "Breeann Flesch",
        "Matthew Nabity"
    ],
    "dcterms:subject": [
        "Probe interval graph",
        "recognition algorithm",
        "2-tree",
        "linear-time algorithm"
    ],
    "dcterms:publisher": [
        "SCIENCEDOMAIN international"
    ],
    "dcterms:date": [
        "9/5/2016"
    ],
    "dcterms:type": [
        "Text"
    ],
    "dcterms:identifier": [
        "fac_pubs/37"
    ],
    "dcterms:source": [
        "British Journal of Mathematics & Computer Science"
    ],
    "dcterms:language": [
        "eng"
    ],
    "dcterms:abstract": [
        "Recognition of probe interval graphs has been studied extensively. Recognition algorithms of probe interval graphs can be broken down into two types of problems: partitioned and non-partitioned. A partitioned recognition algorithm includes the probe and nonprobe partition of the vertices as part of the input, where a non-partitioned algorithm does not include the partition. Partitioned probe interval graphs can be recognized in linear-time in the edges, whereas non-partitioned probe interval graphs can be recognized in polynomial-time. Here we present a non-partitioned recognition algorithm for 2-trees, an extension of trees, that are probe interval graphs. We show that this algorithm runs in O(m) time, where m is the number of edges of a 2-tree. Currently there is no algorithm that performs as well for this problem."
    ],
    "bibo:issue": [
        "4"
    ],
    "bibo:pageEnd": [
        "11"
    ],
    "bibo:pageStart": [
        "1"
    ],
    "bibo:volume": [
        "18"
    ],
    "VIVO:departmentOrSchool": [
        "Mathematics"
    ]
}
]