Sparse balanced partitions and the complexity of subgraph problems

DOI10.1137/100812653MaRDI QIDQ3094934zbMATH OpenOpenAlexFDO

Authors Noga Alon, Dániel Marx

Publication date 27 October 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/16a250b8c22b6cfab6dde5429f34fdbb1712dc0a

zbMATH Keywords

graph partitionssubgraph problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Recommendations

• Graph partitions: recent progresses and some open problems
• Balanced partitions of trees and applications
• Balanced graph partitioning

Cited in

(11)

• Beating treewidth for average-case subgraph isomorphism
• Clustering powers of sparse graphs
• Complexity and inapproximability results for balanced connected subgraph problem
• scientific article; zbMATH DE number 1085970 (Why is no real title available?)
• On the parameterized complexity of computing balanced partitions in graphs
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• On the hardness of the Balanced Connected Subgraph Problem for families of Regular Graphs
• Dense graph partitioning on sparse and dense graphs
• On the complexity of minimizing energy consumption of partitioning DAG tasks
• Can you link up with treewidth?
• Can you link up with treewidth?

This page was built for publication: Sparse balanced partitions and the complexity of subgraph problems

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