Partition into Triangles on Bounded Degree Graphs

DOI10.1007/978-3-642-18381-2_46zbMath1298.68119OpenAlexW1544209192WikidataQ59567611 ScholiaQ59567611MaRDI QIDQ3075543

Johan M. M. van Rooij, Marcel E. van Kooten Niekerk, Hans L. Bodlaender

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_46

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Strong partial clones and the time complexity of SAT problems ⋮ Data stability in clustering: a closer look ⋮ Cluster editing with locally bounded modifications ⋮ On the complexity of some quorum colorings problems of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Which problems have strongly exponential complexity?
• New algorithms for exact satisfiability
• Set Partitioning via Inclusion-Exclusion
• Partitioning into Sets of Bounded Cardinality
• The complexity of satisfiability problems

This page was built for publication: Partition into Triangles on Bounded Degree Graphs