Partition into triangles on bounded degree graphs

DOI10.1007/s00224-012-9412-5zbMath1286.68214WikidataQ59567514 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

algorithms; bounded degree graphs; graph algorithms; satisfiability; exact algorithms; partition into triangles

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Star Partitions of Perfect Graphs, Packing Cycles Faster Than Erdos--Posa, A randomized approximation algorithm for metric triangle packing, Matching cut in graphs with large minimum degree, Scheduling with interjob communication on parallel processors, Geometric versions of the three-dimensional assignment problem under general norms, Two-machine open shop problem with agreement graph, A complexity and approximation framework for the maximization scaffolding problem, 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, Subexponential Time Algorithms for Finding Small Tree and Path Decompositions

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