A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs

DOI10.1007/978-3-540-72504-6_10zbMath1198.68184OpenAlexW1514126475MaRDI QIDQ5425425

Takeaki Uno, Ryuhei Uehara, Shin-ichi Nakano

Publication date: 13 November 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-72504-6_10

zbMATH Keywords

distance-hereditary graphtree representationalgorithmic graph theorycographprefix tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (10)

A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs ⋮ The Weisfeiler-Leman dimension of distance-hereditary graphs ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Enumerations, forbidden subgraph characterizations, and the split-decomposition ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ Simple Geometrical Intersection Graphs ⋮ Laminar structure of ptolemaic graphs with applications

This page was built for publication: A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs