dc.contributor.author | Jeong, Jisu | |
dc.contributor.author | Sæther, Sigve Hortemo | |
dc.contributor.author | Telle, Jan Arne | |
dc.date.accessioned | 2016-05-30T08:17:54Z | |
dc.date.available | 2016-05-30T08:17:54Z | |
dc.date.issued | 2015 | |
dc.identifier.isbn | 978-3-939897-92-7 | |
dc.identifier.issn | 1868-8969 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/12029 | |
dc.description.abstract | We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A \cup B \cup C=X and |A|,|B|,|C| <= k such that any subset of X that is a minimal separator of H is a subset of either A, B or C. Treewidth and branchwidth have alternative definitions through intersections of subtrees, where treewidth focuses on nodes and branchwidth focuses on edges. We show that mm-width combines both aspects, focusing on nodes and on edges. Based on this we prove that given a graph G and a branch decomposition of mm-width k we can solve Dominating Set in time O^*(8^k), thereby beating O^*(3^{tw(G)}) whenever tw(G) > log_3(8) * k ~ 1.893 k. Note that mmw(G) <= tw(G)+1 <= 3 mmw(G) and these inequalities are tight. Given only the graph G and using the best known algorithms to find decompositions, maximum matching width will be better for solving Dominating Set whenever tw(G) > 1.549 * mmw(G). | en_US |
dc.language.iso | eng | eng |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Attribution CC BY 3.0 | eng |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0 | eng |
dc.subject | FPT algorithms | eng |
dc.subject | treewidth | eng |
dc.subject | dominating set | eng |
dc.title | Maximum matching width: New characterizations and a fast algorithm for dominating set | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2016-03-30T10:15:49Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.ipec.2015.212 | |
dc.identifier.cristin | 1344955 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.source.pagenumber | 212-223 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics 2015, 43:212-223 | |
dc.source.volume | 43 | |