Laminar structure of ptolemaic graphs with applications

DOI10.1016/j.dam.2008.09.006zbMath1177.05122OpenAlexW1997722359MaRDI QIDQ1028126

Ryuhei Uehara, Yushi Uno

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.09.006

zbMATH Keywords

data structuresHamiltonian cycletree representationalgorithmic graph theoryptolemaic graphs\(\gamma \)-acyclicityintersection modellaminar structure of cliquesrelational database scheme

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (11)

Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Completion to chordal distance-hereditary graphs: a quartic vertex-kernel ⋮ Polynomial time algorithms for variants of graph matching on partial \(k\)-trees ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ Unnamed Item ⋮ Intersection of longest paths in graph classes ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs ⋮ Enumerations, forbidden subgraph characterizations, and the split-decomposition ⋮ New results on Ptolemaic graphs ⋮ On the Galois lattice of bipartite distance hereditary graphs

Cites Work

• Unnamed Item
• Completely separable graphs
• Distance-hereditary graphs
• On hypergraph acyclicity and graph chordality
• Independent domination in chordal graphs
• Efficient graph representations
• Centers and medians of distance-hereditary graphs
• Algorithmic graph theory and perfect graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• The Hamiltonian problem on distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs
• On the Desirability of Acyclic Database Schemes
• Degrees of acyclicity for hypergraphs and relational database schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Linear Recognition Algorithm for Cographs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A characterization of ptolemaic graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Graph Classes: A Survey
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Efficient Parallel Algorithms for Chordal Graphs
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Combinatorial optimization. Theory and algorithms
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Domination in distance-hereditary graphs

This page was built for publication: Laminar structure of ptolemaic graphs with applications