Efficient enumeration of non-isomorphic interval graphs

DOI10.46298/DMTCS.6164MaRDI QIDQ4987268zbMATH OpenOpenAlexFDO

Authors Patryk Mikos

Publication date 3 May 2021

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1906.04094, https://dmtcs.episciences.org/7246

zbMATH Keywords

combinatoricsenumerationinterval graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. In this paper, we improve their algorithm and achieve $O(n^{3}logn)$ time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all $n$ up to $15$.

Recommendations

• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• On the enumeration of interval graphs
• Efficient enumeration of non-isomorphic Ptolemaic graphs
• Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
• Fast enumeration algorithms for non-crossing geometric graphs
• Fast enumeration algorithms for non-crossing geometric graphs
• Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
• scientific article; zbMATH DE number 6180530
• Efficient enumeration of subgraphs and induced subgraphs with bounded girth

Cited in

(12)

• Efficient enumeration of non-isomorphic distance-hereditary graphs and Ptolemaic graphs
• Succinct encodings for families of interval graphs
• Listing Chordal Graphs and Interval Graphs
• Random Generation and Enumeration of Proper Interval Graphs
• Deferred-query: An efficient approach for some problems on interval graphs
• scientific article; zbMATH DE number 6180530 (Why is no real title available?)
• Fast enumeration algorithms for non-crossing geometric graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• Enumeration of interval graphs and d-representable complexes
• Efficient enumeration of non-isomorphic Ptolemaic graphs

This page was built for publication: Efficient enumeration of non-isomorphic interval graphs

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