KOPS - The Institutional Repository of the University of Konstanz

Treelike Comparability Graphs : Characterization, Recognition, and Applications

Treelike Comparability Graphs : Characterization, Recognition, and Applications

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

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, Jun 21, 2004 - Jun 23, 2004. In: HROMKOVIČ, Juraj, ed. and others. Graph-Theoretic Concepts in Computer Science : 30th International Workshop, WG 2004, Revised Papers. Berlin:Springer, pp. 46-57. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-24132-4. Available under: doi: 10.1007/978-3-540-30559-0_4

@inproceedings{Cornelsen2004Treel-44802, title={Treelike Comparability Graphs : Characterization, Recognition, and Applications}, year={2004}, doi={10.1007/978-3-540-30559-0_4}, number={3353}, isbn={978-3-540-24132-4}, issn={0302-9743}, address={Berlin}, publisher={Springer}, 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 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/rdf/resource/123456789/44802"> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:title>Treelike Comparability Graphs : Characterization, Recognition, and Applications</dcterms:title> <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> <dc:creator>Di Stefano, Gabriele</dc:creator> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-01T13:08:55Z</dc:date> <dc:contributor>Di Stefano, Gabriele</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44802"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-01T13:08:55Z</dcterms:available> <dc:creator>Cornelsen, Sabine</dc:creator> <dcterms:issued>2004</dcterms:issued> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Cornelsen, Sabine</dc:contributor> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account