Publikation:

Blocks of hypergraphs : applied to hypergraphs and outerplanarity

Vorschaubild

Dateien

Brandes etal.pdf
Brandes etal.pdfGröße: 4.34 MBDownloads: 470

Datum

2011

Autor:innen

Sallaberry, Arnaud

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-166041
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-642-19222-7_21
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
Urheberrechtlich geschützt

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

ILIOPOULOS, Costas S., ed., William F. SMYTH, ed.. Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, UK, July 26 - 28, 2010; revised selected papers. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 201-211. Lecture Notes in Computer Science. 6460. ISBN 978-3-642-19221-0. Available under: doi: 10.1007/978-3-642-19222-7_21

Zusammenfassung

A support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a connected subgraph. We show how to test in polynomial time whether a given hypergraph has a cactus support, i.e. a support that is a tree of edges and cycles. While it is NP-complete to decide whether a hypergraph has a 2-outerplanar support, we show how to test in polynomial time whether a hypergraph that is closed under intersections and differences has an outerplanar or a planar support. In all cases our algorithms yield a construction of the required support if it exists. The algorithms are based on a new definition of biconnected components in hypergraphs.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BRANDES, Ulrik, Sabine CORNELSEN, Barbara PAMPEL, Arnaud SALLABERRY, 2011. Blocks of hypergraphs : applied to hypergraphs and outerplanarity. In: ILIOPOULOS, Costas S., ed., William F. SMYTH, ed.. Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, UK, July 26 - 28, 2010; revised selected papers. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 201-211. Lecture Notes in Computer Science. 6460. ISBN 978-3-642-19221-0. Available under: doi: 10.1007/978-3-642-19222-7_21
BibTex
@inproceedings{Brandes2011Block-16604,
  year={2011},
  doi={10.1007/978-3-642-19222-7_21},
  title={Blocks of hypergraphs : applied to hypergraphs and outerplanarity},
  number={6460},
  isbn={978-3-642-19221-0},
  publisher={Springer Berlin Heidelberg},
  address={Berlin, Heidelberg},
  series={Lecture Notes in Computer Science},
  booktitle={Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, UK, July 26 - 28, 2010; revised selected papers},
  pages={201--211},
  editor={Iliopoulos, Costas S. and Smyth, William F.},
  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/16604">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/16604/2/Brandes%20etal.pdf"/>
    <dcterms:issued>2011</dcterms:issued>
    <dc:contributor>Sallaberry, Arnaud</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Pampel, Barbara</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-11-07T13:26:24Z</dc:date>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/16604"/>
    <dc:creator>Sallaberry, Arnaud</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="eng">A support of a hypergraph H is a graph with the same vertex set as H in which each hyperedge induces a connected subgraph. We show how to test in polynomial time whether a given hypergraph has a cactus support, i.e. a support that is a tree of edges and cycles. While it is NP-complete to decide whether a hypergraph has a 2-outerplanar support, we show how to test in polynomial time whether a hypergraph that is closed under intersections and differences has an outerplanar or a planar support. In all cases our algorithms yield a construction of the required support if it exists. The algorithms are based on a new definition of biconnected components in hypergraphs.</dcterms:abstract>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-06-30T22:25:08Z</dcterms:available>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Pampel, Barbara</dc:creator>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:creator>Cornelsen, Sabine</dc:creator>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dc:language>eng</dc:language>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/16604/2/Brandes%20etal.pdf"/>
    <dcterms:title>Blocks of hypergraphs : applied to hypergraphs and outerplanarity</dcterms:title>
    <dcterms:bibliographicCitation>First publ. in: Combinatorial algorithms : 21st International Workshop, IWOCA 2010, London, UK, July 26 - 28, 2010; revised selected papers / Costas S. Iliopoulos ... (eds.). Berlin [u.a.] : Springer, 2011. - S. 201-211 (Lecture Notes in Computer Science ; 6460). - ISBN 978-3-642-19221-0</dcterms:bibliographicCitation>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen