Linear-time generation of random chordal graphs

DOI10.1007/978-3-319-57586-5_37zbMATH Open1486.68138OpenAlexW2606249259MaRDI QIDQ5283388FDOQ5283388

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

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

Recommendations

• Generation of random chordal graphs using subtrees of a tree
• An efficient representation of chordal graphs
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• Algorithms for generating strongly chordal graphs
• Two methods for the generation of chordal graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• On rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Subset feedback vertex sets in chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in chordal graphs
• Minimal triangulations of graphs: a survey
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Parameterized coloring problems on chordal graphs
• Title not available (Why is that?)
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• A characterisation of rigid circuit graphs
• Approximating interval coloring and max-coloring in chordal graphs
• Two methods for the generation of chordal graphs
• On Generating Random Network Structures: Trees
• Experimental and Efficient Algorithms

Cited In (14)

• On listing, sampling, and counting the chordal graphs with edge constraints
• Generating Random Hyperbolic Graphs in Subquadratic Time
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• 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
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Algorithms for generating strongly chordal graphs
• A separator-based method for generating weakly chordal graphs
• Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford
• Listing Chordal Graphs and Interval Graphs
• Cograph generation with linear delay
• Generation of random chordal graphs using subtrees of a tree
• Two methods for the generation of chordal graphs
• Title not available (Why is that?)

This page was built for publication: Linear-time generation of random chordal graphs

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