The recognition of geodetically connected graphs

DOI10.1016/S0020-0190(97)00201-9zbMath1338.68214OpenAlexW2005122393MaRDI QIDQ293190

Jou-Ming Chang, Chin-Wen Ho

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019097002019?np=y

zbMATH Keywords

geodetically connectedhinge verticesrecognition algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Minimumk-geodetically connected digraphs ⋮ Towards minimumk-geodetically connected graphs ⋮ Erratum and addendum to ``A linear time algorithm for finding all hinge vertices of a permutation graph ⋮ Some special minimum \(k\)-geodetically connected graphs ⋮ An efficient distributed algorithm for finding all hinge vertices in networks

Cites Work

• Unnamed Item
• Unnamed Item
• A linear time algorithm for finding all hinge vertices of a permutation graph
• Matrix multiplication via arithmetic progressions
• Characterizations of strongly chordal graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A recognition algorithm for the intersection graphs of paths in trees
• Parallel concepts in graph theory
• Doubly lexical ordering of dense 0--1 matrices
• Incidence matrices and interval graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Convexity in Graphs and Hypergraphs
• Three Partition Refinement Algorithms
• A characterization of ptolemaic graphs
• Geodetic connectivity of graphs
• 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 Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: The recognition of geodetically connected graphs