A separator-based method for generating weakly chordal graphs

DOI10.1142/S1793830920500391MaRDI QIDQ5858151zbMATH OpenFDO

Authors Md. Zamilur Rahman, Asish Mukhopadhyay, Y. P. Aneja

Publication date 9 April 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.01056

zbMATH Keywords

data structuresgraph algorithmsgraph generationweakly chordal graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: We propose a scheme for generating a weakly chordal graph on n vertices with m edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the n vertices) based on this tree. In the next and final step, we insert additional edges to give us a weakly chordal graph on m edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is O(n^3) time and an insertion takes constant time. On the other hand, a generation algorithm based on finding a 2-pair takes O(nm) time using the algorithm of Arikati and Rangan [1].

Recommendations

• Two methods for the generation of chordal graphs
• Generating weakly triangulated graphs
• Maintaining graph properties of weakly chordal graphs
• Linear-time generation of random chordal graphs
• Improved algorithms for weakly chordal graphs

Cites work

• Algorithms for weakly triangulated graphs
• An efficient algorithm for finding a two-pair, and its applications
• Generating random regular graphs
• Generating Random Unlabelled Graphs
• Generating weakly triangulated graphs
• scientific article; zbMATH DE number 15335 (Why is no real title available?)
• Improved algorithms for weakly chordal graphs
• Incidence matrices and interval graphs
• Linear layouts of weakly triangulated graphs
• Linear-time generation of random chordal graphs
• Optimizing weakly triangulated graphs
• Two methods for the generation of chordal graphs
• Uniform generation of random regular graphs of moderate degree
• Weakly triangulated graphs

Cited in

(3)

• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• Algorithms for generating strongly chordal graphs
• Generating weakly chordal graphs from arbitrary graphs

This page was built for publication: A separator-based method for generating weakly chordal graphs

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