Laminar structure of ptolemaic graphs with applications
DOI10.1016/J.DAM.2008.09.006zbMATH Open1177.05122OpenAlexW1997722359MaRDI QIDQ1028126FDOQ1028126
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
data structuresHamiltonian cycletree representationptolemaic graphs\(\gamma \)-acyclicityalgorithmic graph theoryintersection modellaminar structure of cliquesrelational database scheme
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Efficient graph representations
- Algorithmic graph theory and perfect graphs
- Distance-hereditary graphs
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- On the Desirability of Acyclic Database Schemes
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A Linear Recognition Algorithm for Cographs
- A characterization of ptolemaic graphs
- A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
- The Hamiltonian problem on distance-hereditary graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Independent domination in chordal graphs
- Degrees of acyclicity for hypergraphs and relational database schemes
- On hypergraph acyclicity and graph chordality
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- Completely separable graphs
- A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
- Centers and medians of distance-hereditary graphs
- Combinatorial optimization. Theory and algorithms
- Efficient Parallel Algorithms for Chordal Graphs
- Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
- Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Domination in distance-hereditary graphs
Cited In (13)
- Title not available (Why is that?)
- On the Galois lattice of bipartite distance hereditary graphs
- Computing the union join and subset graph of acyclic hypergraphs in subquadratic time
- Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
- Polynomial time algorithms for variants of graph matching on partial \(k\)-trees
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs
- Shared ancestry graphs and symbolic arboreal maps
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Recognition of Probe Ptolemaic Graphs
- Intersection of longest paths in graph classes
- New results on Ptolemaic graphs
- Enumerations, forbidden subgraph characterizations, and the split-decomposition
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Lattice structures from planar graphs 👍 👎
- Combinatorial and Geometric Properties of Planar Laman Graphs 👍 👎
- On the geometry and Laplacian of a graph 👍 👎
- Ptolemaic and planar cover-incomparability graphs 👍 👎
- A structural theorem for planar graphs with some applications 👍 👎
- Geometric Graphs in the Plane Lattice 👍 👎
- Axiomatic characterizations of Ptolemaic and chordal graphs 👍 👎
This page was built for publication: Laminar structure of ptolemaic graphs with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028126)
