The recognition of geodetically connected graphs

DOI10.1016/S0020-0190(97)00201-9MaRDI QIDQ293190zbMATHOpenAlexFDO

Authors 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

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

Recommendations

• Towards minimumk-geodetically connected graphs
• Some special minimum \(k\)-geodetically connected graphs
• Minimumk-geodetically connected digraphs
• Minimum 3-geodetically connected graphs
• The optimal sequential and parallel algorithms to compute all hinge vertices on interval graphs

Cites work

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

Cited in

(8)

• An efficient distributed algorithm for finding all hinge vertices in networks
• Minimumk-geodetically connected digraphs
• An efficient algorithm for finding all hinge vertices on trapezoid graphs
• Some special minimum \(k\)-geodetically connected graphs
• Towards minimumk-geodetically connected graphs
• Recognition of Probe Ptolemaic Graphs
• Erratum and addendum to ``A linear time algorithm for finding all hinge vertices of a permutation graph
• Recognizing hinge-free line graphs and total graphs

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

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