Partition into triangles on bounded degree graphs

DOI10.1007/s00224-012-9412-5zbMath1286.68214OpenAlexW2069561762WikidataQ59567514 ScholiaQ59567514MaRDI QIDQ2392247

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

Publication date: 1 August 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9412-5

zbMATH Keywords

algorithmsbounded degree graphsgraph algorithmssatisfiabilityexact algorithmspartition into triangles

Mathematics Subject Classification ID

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

Scheduling with interjob communication on parallel processors, Subexponential Time Algorithms for Finding Small Tree and Path Decompositions, The complexity of degree anonymization by graph contractions, An improved kernel for planar vertex-disjoint triangle packing, On the parameterized complexity of clustering problems for incomplete data, Geometric versions of the three-dimensional assignment problem under general norms, Star Partitions of Perfect Graphs, A randomized approximation algorithm for metric triangle packing, Matching cut in graphs with large minimum degree, Packing Cycles Faster Than Erdos--Posa, Two-machine open shop problem with agreement graph, A complexity and approximation framework for the maximization scaffolding problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for four variants of the exact satisfiability problem
• Exact exponential algorithms.
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Exact algorithms for exact satisfiability and number of perfect matchings
• An algorithm for exact satisfiability analysed with the number of clauses as parameter
• Which problems have strongly exponential complexity?
• New algorithms for exact satisfiability
• Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
• Faster exact solutions for some NP-hard problems.
• Fast algorithms for max independent set
• Set Partitioning via Inclusion-Exclusion
• Partitioning into Sets of Bounded Cardinality
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• The complexity of satisfiability problems
• On the complexity of \(k\)-SAT