Generating weakly chordal graphs from arbitrary graphs

DOI10.1007/978-3-662-66491-9_4MaRDI QIDQ6111462zbMATH OpenOpenAlexFDO

Authors Sudiksha Khanduja, Aayushi Srivastava, Md. Zamilur Rahman, Asish Mukhopadhyay

Publication date 3 August 2023

Published in Transactions on Computational Science XXXIX (Search for Journal in Brave)

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

zbMATH Keywords

minimum triangulationweak triangulationweakly chordal graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We propose a scheme for generating a weakly chordal graph from a randomly generated input graph, G = (V, E). We reduce G to a chordal graph H by adding fill-edges, using the minimum vertex degree heuristic. Since H is necessarily a weakly chordal graph, we use an algorithm for deleting edges from a weakly chordal graph that preserves the weak chordality property of H. The edges that are candidates for deletion are the fill-edges that were inserted into G. In order to delete a maximal number of fill-edges, we maintain these in a queue. A fill-edge is removed from the front of the queue, which we then try to delete from H. If this violates the weak chordality property of H, we reinsert this edge at the back of the queue. This loop continues till no more fill-edges can be removed from H. Operationally, we implement this by defining a deletion round as one in which the edge at the back of the queue is at the front.We stop when the size of the queue does not change over two successive deletion rounds and output H.

Recommendations

• Generating weakly triangulated graphs
• A separator-based method for generating weakly chordal graphs
• Algorithms for generating strongly chordal graphs
• Weakly triangulated graphs
• On self-complementary weakly chordal graphs

Cites work

• A separator-based method for generating weakly chordal graphs
• Algorithms for weakly triangulated graphs
• Cataloguing the graphs on 10 vertices
• Computing the Minimum Fill-In is NP-Complete
• scientific article; zbMATH DE number 15335 (Why is no real title available?)
• scientific article; zbMATH DE number 1305489 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• Improved algorithms for weakly chordal graphs
• Linear layouts of weakly triangulated graphs
• Optimizing weakly triangulated graphs
• Recognizing weakly triangulated graphs by edge separability
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• The Evolution of the Minimum Degree Ordering Algorithm
• Treewidth and minimum fill-in: Grouping the minimal separators
• Weakly triangulated graphs

Cited in

(1)

• Generating weakly triangulated graphs

This page was built for publication: Generating weakly chordal graphs from arbitrary graphs

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