Recognizing Helly edge-path-tree graphs and their clique graphs

DOI10.1016/J.DAM.2011.02.008MaRDI QIDQ2275917zbMATH OpenOpenAlexFDO

Authors Nicola Apollonio, Massimiliano Caramia

Publication date 10 August 2011

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

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

zbMATH Keywords

clique graphsedge-path-tree graphsedge-path-tree matricesHelly property

Mathematics Subject Classification ID

Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 4116559
• Helly EPT graphs on bounded degree trees: characterization and recognition
• scientific article; zbMATH DE number 1409177
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• The edge intersection graphs of paths in a tree

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• A superclass of edge-path-tree graphs with few cliques
• Algorithm Theory - SWAT 2004
• An Almost Linear-Time Algorithm for Graph Realization
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Characterizations of strongly chordal graphs
• Combinatorial Configurations
• Combinatorial optimization. Packing and covering
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Converting Linear Programs to Network Problems
• Edge and vertex intersection of paths in a tree
• Graph Classes: A Survey
• scientific article; zbMATH DE number 3884212 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4010523 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 53949 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 553916 (Why is no real title available?)
• scientific article; zbMATH DE number 863476 (Why is no real title available?)
• Hypergraphes de chaînes d'aretes d'un arbre
• Integrality properties of edge path tree families
• Intersection graphs of paths in a tree
• Intersection representations of graphs by arcs
• Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion
• Recognizing clique graphs of directed and rooted path graphs
• Recognizing clique graphs of directed edge path graphs
• The arborescence-realization problem
• The edge intersection graphs of paths in a tree
• Triangulated edge intersection graphs of paths in a tree

Cited in

(10)

• Recognizing clique graphs of directed and rooted path graphs
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Helly EPT graphs on bounded degree trees: characterization and recognition
• Simplicial complexes and closure systems induced by indistinguishability relations
• Edge contraction and edge removal on iterated clique graphs
• The maximum vertex coverage problem on bipartite graphs
• Strong cliques and equistability of EPT graphs
• scientific article; zbMATH DE number 942492 (Why is no real title available?)
• scientific article; zbMATH DE number 4116559 (Why is no real title available?)
• Indiscernibility structures induced from function sets: graph and digraph case

This page was built for publication: Recognizing Helly edge-path-tree graphs and their clique graphs

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