Linear-Time Generation of Random Chordal Graphs

DOI10.1007/978-3-319-57586-5_37zbMath1486.68138OpenAlexW2606249259MaRDI QIDQ5283388

Pinar Heggernes, Z. Caner Taşkın, Oylum Şeker, Tınaz Ekim

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-57586-5_37

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Algorithms for generating strongly chordal graphs ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation ⋮ An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs ⋮ A separator-based method for generating weakly chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in chordal graphs
• On rigid circuit graphs
• Minimal triangulations of graphs: a survey
• Parameterized coloring problems on chordal graphs
• Two methods for the generation of chordal graphs
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Subset feedback vertex sets in chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Approximating interval coloring and max-coloring in chordal graphs
• On Generating Random Network Structures: Trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph Classes: A Survey
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Experimental and Efficient Algorithms

This page was built for publication: Linear-Time Generation of Random Chordal Graphs