Publikation: Treelike Comparability Graphs : Characterization, Recognition, and Applications
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2004
Autor:innen
Di Stefano, Gabriele
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
HROMKOVIČ, Juraj, ed. and others. Graph-Theoretic Concepts in Computer Science : 30th International Workshop, WG 2004, Revised Papers. Berlin: Springer, 2004, pp. 46-57. Lecture Notes in Computer Science. 3353. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-24132-4. Available under: doi: 10.1007/978-3-540-30559-0_4
Zusammenfassung
An undirected graph is a treelike comparability graph if it admits a transitive orientation such that its transitive reduction is a tree. We show that treelike comparability graphs are distance hereditary. Utilizing this property, we give a linear time recognition algorithm. We then characterize permutation graphs that are treelike. Finally, we consider the Partitioning into Bounded Cliques problem on special subgraphs of treelike permutation graphs.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Linear Time, Connected Graph, Undirected Graph, Interval Graph, Comparability Graph
Konferenz
Graph-Theoretic Concepts in Computer Science : 30th International Workshop, WG 2004, 21. Juni 2004 - 23. Juni 2004, Bad Honnef, Germany
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
CORNELSEN, Sabine, Gabriele DI STEFANO, 2004. Treelike Comparability Graphs : Characterization, Recognition, and Applications. Graph-Theoretic Concepts in Computer Science : 30th International Workshop, WG 2004. Bad Honnef, Germany, 21. Juni 2004 - 23. Juni 2004. In: HROMKOVIČ, Juraj, ed. and others. Graph-Theoretic Concepts in Computer Science : 30th International Workshop, WG 2004, Revised Papers. Berlin: Springer, 2004, pp. 46-57. Lecture Notes in Computer Science. 3353. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-24132-4. Available under: doi: 10.1007/978-3-540-30559-0_4BibTex
@inproceedings{Cornelsen2004Treel-44802, year={2004}, doi={10.1007/978-3-540-30559-0_4}, title={Treelike Comparability Graphs : Characterization, Recognition, and Applications}, number={3353}, isbn={978-3-540-24132-4}, issn={0302-9743}, publisher={Springer}, address={Berlin}, series={Lecture Notes in Computer Science}, booktitle={Graph-Theoretic Concepts in Computer Science : 30th International Workshop, WG 2004, Revised Papers}, pages={46--57}, editor={Hromkovič, Juraj}, author={Cornelsen, Sabine and Di Stefano, Gabriele} }
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/44802"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:abstract xml:lang="eng">An undirected graph is a treelike comparability graph if it admits a transitive orientation such that its transitive reduction is a tree. We show that treelike comparability graphs are distance hereditary. Utilizing this property, we give a linear time recognition algorithm. We then characterize permutation graphs that are treelike. Finally, we consider the Partitioning into Bounded Cliques problem on special subgraphs of treelike permutation graphs.</dcterms:abstract> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-01T13:08:55Z</dcterms:available> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-01T13:08:55Z</dc:date> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44802"/> <dc:creator>Cornelsen, Sabine</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:issued>2004</dcterms:issued> <dcterms:title>Treelike Comparability Graphs : Characterization, Recognition, and Applications</dcterms:title> <dc:contributor>Di Stefano, Gabriele</dc:contributor> <dc:creator>Di Stefano, Gabriele</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/"/> </rdf:Description> </rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein