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

DOI10.1007/978-3-540-72504-6_10MaRDI QIDQ5425425zbMATH OpenOpenAlexFDO

Authors Ryuhei Uehara, Takeaki Uno, 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 graphcographtree representationprefix treealgorithmic graph theory

Mathematics Subject Classification ID

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

Recommendations

• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• scientific article; zbMATH DE number 1501961

Cited in

(13)

• Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
• Simple Geometrical Intersection Graphs
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• An exact enumeration of distance-hereditary graphs
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• Tractabilities and intractabilities on geometric intersection graphs
• Random Generation and Enumeration of Proper Interval Graphs
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• Succinct data structures for bounded clique-width graphs
• Towards an isomorphism dichotomy for hereditary graph classes
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Laminar structure of ptolemaic graphs with applications
• Enumerations, forbidden subgraph characterizations, and the split-decomposition

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5425425)