On the complexity of problems on graphs defined on groups

DOI10.1007/978-3-032-04700-7_11MaRDI QIDQ6852232zbMATH OpenFDO

Authors Bireswar Das, Dipan Dey, Jinia Ghosh

Publication date 26 February 2026

Full work available at URL https://doi.org/10.1007/978-3-032-04700-7_11

zbMATH Keywords

complexity theoryexponential time hypothesisgraph motifgraphs defined on groupspower graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Algorithmic meta-theorems for restrictions of treewidth
• Deterministic parameterized algorithms for the graph motif problem
• Enumerating p -Groups. I: Inequalities
• ENUMERATING FINITE GROUPS
• Finding and counting vertex-colored subtrees
• Geometric algorithms and combinatorial optimization
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graphs defined on groups
• scientific article; zbMATH DE number 1318518 (Why is no real title available?)
• scientific article; zbMATH DE number 2018401 (Why is no real title available?)
• scientific article; zbMATH DE number 1522659 (Why is no real title available?)
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• On the structure of the power graph and the enhanced power graph of a group
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Succinct representation of finite abelian groups
• The graph motif problem parameterized by the structure of the input graph
• The Polycyclic Length of Linear and Finite Polycyclic Groups
• Undirected power graphs of semigroups
• Which problems have strongly exponential complexity?

This page was built for publication: On the complexity of problems on graphs defined on groups

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