Path-based supports for hypergraphs

A path-based support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a Hamiltonian subgraph. While it is NP-hard to decide whether a path-based support has a monotone drawing, to determine a path-based support with the minimum number of edges, or to decide whether there is a planar path-based support, we show that a path-based tree support can be computed in polynomial time if it exists.

Subject (DDC)

004 Computer Science

Cite This

ISO 690

BRANDES, Ulrik, Sabine CORNELSEN, Barbara PAMPEL, Arnaud SALLABERRY, 2012. Path-based supports for hypergraphs. In: Journal of Discrete Algorithms. 14, pp. 248-261. ISSN 1570-8667. eISSN 1570-8667. Available under: doi: 10.1016/j.jda.2011.12.009

BibTex

@article{Brandes2012Pathb-20925,
  year={2012},
  doi={10.1016/j.jda.2011.12.009},
  title={Path-based supports for hypergraphs},
  volume={14},
  issn={1570-8667},
  journal={Journal of Discrete Algorithms},
  pages={248--261},
  author={Brandes, Ulrik and Cornelsen, Sabine and Pampel, Barbara and Sallaberry, Arnaud}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/20925">
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Sallaberry, Arnaud</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20925/2/Brandes_209250.pdf"/>
    <dcterms:bibliographicCitation>Journal of Discrete Algorithms ; 14 (2012). - S. 248-261</dcterms:bibliographicCitation>
    <dcterms:issued>2012</dcterms:issued>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/20925/2/Brandes_209250.pdf"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-11-23T08:56:13Z</dc:date>
    <dcterms:abstract>A path-based support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a Hamiltonian subgraph. While it is NP-hard to decide whether a path-based support has a monotone drawing, to determine a path-based support with the minimum number of edges, or to decide whether there is a planar path-based support, we show that a path-based tree support can be computed in polynomial time if it exists.</dcterms:abstract>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dc:contributor>Sallaberry, Arnaud</dc:contributor>
    <dc:contributor>Pampel, Barbara</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:title>Path-based supports for hypergraphs</dcterms:title>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/20925"/>
    <dc:creator>Pampel, Barbara</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-11-23T08:56:13Z</dcterms:available>
    <dc:language>eng</dc:language>
  </rdf:Description>
</rdf:RDF>

Bibliography of Konstanz

Yes