GLORIA

GEOMAR Library Ocean Research Information Access

X

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Association for Computing Machinery (ACM)  (30)
  • 1
    Online Resource
    Online Resource
    Combinatorial bounds via measure and conquer : Bounding minimal dominating sets and applications
    Association for Computing Machinery (ACM) ; 2008
    In:  ACM Transactions on Algorithms Vol. 5, No. 1 ( 2008-11), p. 1-17
    Details
    In: ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 5, No. 1 ( 2008-11), p. 1-17
    Abstract: We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O (1.7159 n ). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159 n , thus improving on the trivial O (2 n /√ n ) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O (2.8718 n ) algorithm for the domatic number problem.
    Type of Medium: Online Resource
    ISSN: 1549-6325 , 1549-6333
    URL: Article
    DOI: 10.1145/1435375.1435384
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2008
    detail.hit.zdb_id: 2198259-4
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 2
    Online Resource
    Online Resource
    Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
    Association for Computing Machinery (ACM) ; 2016
    In:  Journal of the ACM Vol. 63, No. 4 ( 2016-11-08), p. 1-60
    Details
    In: Journal of the ACM, Association for Computing Machinery (ACM), Vol. 63, No. 4 ( 2016-11-08), p. 1-60
    Abstract: Let M =( E , I ) be a matroid and let S ={ S 1 , ċ , S t } be a family of subsets of E of size p . A subfamily Ŝ ⊆ S is q - representative for S if for every set Y ⊆ E of size at most q , if there is a set X ∈ S disjoint from Y with X ∪ Y ∈ I , then there is a set Xˆ ∈ Ŝ disjoint from Y with Xˆ ∪ Y ∈ I . By the classic result of Bollobás, in a uniform matroid, every family of sets of size p has a q -representative family with at most ( p + q p ) sets. In his famous “two families theorem” from 1977, Lovász proved that the same bound also holds for any matroid representable over a field F. We give an efficient construction of a q -representative family of size at most ( p + q p ) in time bounded by a polynomial in ( p + q p ), t , and the time required for field operations. We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following: —In the L ong D irected C ycle problem, the input is a directed n -vertex graph G and the positive integer k . The task is to find a directed cycle of length at least k in G , if such a cycle exists. As a consequence of our 6.75 k + o ( k ) n O (1) time algorithm, we have that a directed cycle of length at least log n , if such a cycle exists, can be found in polynomial time. —In the M inimum E quivalent G raph (MEG) problem, we are seeking a spanning subdigraph D ′ of a given n -vertex digraph D with as few arcs as possible in which the reachability relation is the same as in the original digraph D . —We provide an alternative proof of the recent results for algorithms on graphs of bounded treewidth showing that many “connectivity” problems such as H amiltonian C ycle or S teiner T ree can be solved in time 2 O ( t ) n on n -vertex graphs of treewidth at most t . For the special case of uniform matroids on n elements, we give a faster algorithm to compute a representative family. We use this algorithm to provide the fastest known deterministic parameterized algorithms for k -P ath , k -T ree , and, more generally, k -S ubgraph I somorphism , where the k -vertex pattern graph is of constant treewidth.
    Type of Medium: Online Resource
    ISSN: 0004-5411 , 1557-735X
    URL: Article
    DOI: 10.1145/2886094
    RVK:
    SA 3010
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2016
    detail.hit.zdb_id: 2006500-0
    detail.hit.zdb_id: 6759-3
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 3
    Online Resource
    Online Resource
    Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes
    Association for Computing Machinery (ACM) ; 2018
    In:  Journal of the ACM Vol. 65, No. 2 ( 2018-04-30), p. 1-44
    Details
    In: Journal of the ACM, Association for Computing Machinery (ACM), Vol. 65, No. 2 ( 2018-04-30), p. 1-44
    Abstract: Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker’s approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including C onnected D ominating S et and F eedback V ertex S et . In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t × t grid as a minor guarantees that the treewidth of G is subquadratic in t . For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for “most” bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G ϵ G as input and an ϵ 〉 0, outputs a vertex set X of size ϵ ċ OPT such that the treewidth of G - X is f (ϵ). Here, OPT is the objective function value of the problem in question and f is a function depending only on ϵ. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems—including C ycle P acking , F -P acking , F -D eletion , M ax L eaf S panning T ree , or P artial r -D ominating S et —no EPTASs, even on planar graphs, were previously known. We also prove novel excluded grid theorems in unit disk and map graphs without large cliques. Using these theorems, we show that these classes of graphs have the SQGM property. Based on the developed framework, we design EPTASs and subexponential time parameterized algorithms for various classes of problems on unit disk and map graphs.
    Type of Medium: Online Resource
    ISSN: 0004-5411 , 1557-735X
    URL: Article
    DOI: 10.1145/3154833
    RVK:
    SA 3010
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2018
    detail.hit.zdb_id: 2006500-0
    detail.hit.zdb_id: 6759-3
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 4
    Online Resource
    Online Resource
    Exact exponential algorithms
    Association for Computing Machinery (ACM) ; 2013
    In:  Communications of the ACM Vol. 56, No. 3 ( 2013-03), p. 80-88
    Details
    In: Communications of the ACM, Association for Computing Machinery (ACM), Vol. 56, No. 3 ( 2013-03), p. 80-88
    Abstract: Discovering surprises in the face of intractability.
    Type of Medium: Online Resource
    ISSN: 0001-0782 , 1557-7317
    URL: Article
    DOI: 10.1145/2428556.2428575
    RVK:
    SA 3000
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2013
    detail.hit.zdb_id: 80254-2
    detail.hit.zdb_id: 2004542-6
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 5
    Online Resource
    Online Resource
    Subexponential Parameterized Algorithm for I nterval C ompletion
    Association for Computing Machinery (ACM) ; 2018
    In:  ACM Transactions on Algorithms Vol. 14, No. 3 ( 2018-07-31), p. 1-62
    Details
    In: ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 14, No. 3 ( 2018-07-31), p. 1-62
    Abstract: In the I nterval C ompletion problem we are given an n -vertex graph G and an integer k , and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of I nterval C ompletion was asked by Kaplan et al. [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger et al. [STOC 2007; SIAM J. Comput. 2009] , who presented an algorithm with running time O ( k 2 k n 3 m ). We give the first subexponential parameterized algorithm solving I nterval C ompletion in time k O (√ k ) n O (1) . This adds I nterval C ompletion to a very small list of parameterized graph modification problems solvable in subexponential time.
    Type of Medium: Online Resource
    ISSN: 1549-6325 , 1549-6333
    URL: Article
    DOI: 10.1145/3186896
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2018
    detail.hit.zdb_id: 2198259-4
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 6
    Online Resource
    Online Resource
    Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
    Association for Computing Machinery (ACM) ; 2005
    In:  ACM Transactions on Algorithms Vol. 1, No. 1 ( 2005-07), p. 33-47
    Details
    In: ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 1, No. 1 ( 2005-07), p. 33-47
    Abstract: The ( k , r )-center problem asks whether an input graph G has ≤ k vertices (called centers ) such that every vertex of G is within distance ≤ r from some center. In this article, we prove that the ( k , r )-center problem, parameterized by k and R , is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity f ( k , r ) n O (1) where the function f is independent of n . In particular, we show that f ( k,r ) = 2 O ( r log r ) √k , where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of map graphs introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of k and r . Finally, a byproduct of our algorithm is the existence of a PTAS for the r -domination problem in both planar graphs and map graphs.Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are “large” on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.
    Type of Medium: Online Resource
    ISSN: 1549-6325 , 1549-6333
    URL: Article
    DOI: 10.1145/1077464.1077468
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2005
    detail.hit.zdb_id: 2198259-4
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 7
    Online Resource
    Online Resource
    Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
    Association for Computing Machinery (ACM) ; 2018
    In:  ACM Transactions on Algorithms Vol. 14, No. 1 ( 2018-01-31), p. 1-31
    Details
    In: ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 14, No. 1 ( 2018-01-31), p. 1-31
    Abstract: We give the first linear kernels for the D ominating S et and C onnected D ominating S et problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H -topological-minor-free  graph G and a positive integer k , output an H -topological-minor-free  graph G ′ on O ( k ) vertices such that G has a (connected) dominating set of size k if and only if G ′ has one. Our results extend the known classes of graphs on which the D ominating S et and C onnected D ominating S et problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for D ominating S et , a kernel of size k c ( H ) , where c ( H ) is a constant depending on the size of H , follows from a more general result on the kernelization of D ominating S et on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for D ominating S et on H -minor-free  graphs. We answer this question in the affirmative and in fact prove a more general result. For C onnected D ominating S et no polynomial kernel even on H -minor-free  graphs was known prior to our work. On the negative side, it is known that C onnected D ominating S et on 2-degenerated graphs does not admit a polynomial kernel unless coNP ⊆ NP/poly. Our kernelization algorithm is based on a non-trivial combination of the following ingredients • The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor; • A novel notion of protrusions, different than the one defined in [FOCS 2009]; • Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H -minor-free) of the problem, with treewidth O (√ k ). The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels. A protrusion in a graph [FOCS 2009] is a subgraph of constant treewidth which is separated from the rest of the graph by at most a constant number of vertices. In our variant of protrusions, instead of stipulating that the subgraph be of constant treewidth , we ask that it contains a constant number of vertices from a solution . We believe that this new take on protrusions would be useful for other graph problems and in different algorithmic settings.
    Type of Medium: Online Resource
    ISSN: 1549-6325 , 1549-6333
    URL: Article
    DOI: 10.1145/3155298
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2018
    detail.hit.zdb_id: 2198259-4
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 8
    Online Resource
    Online Resource
    Clique-width III : Hamiltonian Cycle and the Odd Case of Graph Coloring
    Association for Computing Machinery (ACM) ; 2019
    In:  ACM Transactions on Algorithms Vol. 15, No. 1 ( 2019-01-31), p. 1-27
    Details
    In: ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 15, No. 1 ( 2019-01-31), p. 1-27
    Abstract: M AX -C UT , E DGE D OMINATING S ET , G RAPH C OLORING , and H AMILTONIAN C YCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO 2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle’s theorem), but cannot be formulated in MSO 1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g ( k ) n f ( k ) on graphs of clique-width k . Fomin et al. (2010) showed that the running times cannot be improved to g ( k ) n O (1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f ( k ) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for E DGE D OMINATING S ET and M AX -C UT to n O ( k ) , and proved that these problems cannot be solved in time g ( k ) n o ( k ) unless ETH fails. Thus, prior to this work, E DGE D OMINATING S ET and M AX -C UT were known to have tight n Θ ( k ) algorithmic upper and lower bounds. In this article, we provide lower bounds for H AMILTONIAN C YCLE and G RAPH C OLORING . For H AMILTONIAN C YCLE , our lower bound g ( k ) n o ( k ) matches asymptotically the recent upper bound n O ( k ) due to Bergougnoux, Kanté, and Kwon (2017). As opposed to the asymptotically tight n Θ( k ) bounds for E DGE D OMINATING S ET , M AX -C UT , and H AMILTONIAN C YCLE , the G RAPH C OLORING problem has an upper bound of n O (2 k ) and a lower bound of merely n o (√ [4] k ) (implicit from the W[1]-hardness proof). In this article, we close the gap for G RAPH C OLORING by proving a lower bound of n 2 o ( k ) . This shows that G RAPH C OLORING behaves qualitatively different from the other three problems. To the best of our knowledge, G RAPH C OLORING is the first natural problem known to require exponential dependence on the parameter in the exponent of n .
    Type of Medium: Online Resource
    ISSN: 1549-6325 , 1549-6333
    URL: Article
    DOI: 10.1145/3280824
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2019
    detail.hit.zdb_id: 2198259-4
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 9
    Online Resource
    Online Resource
    Distortion is Fixed Parameter Tractable
    Association for Computing Machinery (ACM) ; 2013
    In:  ACM Transactions on Computation Theory Vol. 5, No. 4 ( 2013-11), p. 1-20
    Details
    In: ACM Transactions on Computation Theory, Association for Computing Machinery (ACM), Vol. 5, No. 4 ( 2013-11), p. 1-20
    Abstract: We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M ( G ) be the shortest path metric of an edge-weighted graph G , with the vertex set V ( G ) and the edge set E ( G ), on n vertices. We give the first fixed parameter tractable algorithm that for an unweighted graph metric M and integer d either constructs an embedding of M into the line with distortion at most d , or concludes that no such embedding exists. Our algorithm requires O ( nd 4 (2 d + 1) 2d ) time which is a significant improvement over the best previous algorithm that runs in time O ( n 4d+2 d O(1) ). Because of its apparent similarity to the notoriously hard Bandwidth Minimization problem, we find it surprising that this problem turns out to be fixed parameter tractable. We extend our results on embedding unweighted graph metric into the line in two ways. First, we give an algorithm to construct small-distortion embeddings of weighted graph metrics. The running time of our algorithm is O ( n ( dW ) 4 (2 d + 1) 2dW ), where W is the largest edge weight of the input graph. To complement this result, we show that the exponential dependence on the maximum edge weight is unavoidable. In particular, we show that deciding whether a weighted graph metric M ( G ) with maximum weight W 〈 | V ( G )| can be embedded into the line with distortion at most d is NP-complete for every fixed rational d ≥ 2. This rules out any possibility of an algorithm with running time O (( nW ) h(d) ) where h is a function of d alone. Second, we consider more general host metrics for which analogous results hold. In particular, we prove that for any tree T with maximum degree Δ , embedding M into a shortest path metric of T is fixed parameter tractable, parameterized by ( Δ , d ).
    Type of Medium: Online Resource
    ISSN: 1942-3454 , 1942-3462
    URL: Article
    DOI: 10.1145/2489789
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2013
    detail.hit.zdb_id: 2488065-6
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 10
    Online Resource
    Online Resource
    Exploring the Subexponential Complexity of Completion Problems
    Association for Computing Machinery (ACM) ; 2015
    In:  ACM Transactions on Computation Theory Vol. 7, No. 4 ( 2015-09-11), p. 1-38
    Details
    In: ACM Transactions on Computation Theory, Association for Computing Machinery (ACM), Vol. 7, No. 4 ( 2015-09-11), p. 1-38
    Abstract: Let F be a family of graphs. In the F -C ompletion problem, we are given an n -vertex graph G and an integer k as input, and asked whether at most k edges can be added to G so that the resulting graph does not contain a graph from F as an induced subgraph. It was shown recently that two special cases of F -C ompletion , namely, (i) the problem of completing into a chordal graph known as M inimum F ill-in (SIAM J. Comput. 2013), which corresponds to the case of F ={ C 4 , C 5 , C 6 , …}, and (ii) the problem of completing into a split graph (Algorithmica 2015), that is, the case of F ={ C 4 , 2 K 2 , C 5 }, are solvable in parameterized subexponential time 2 O (√ k log k ) n O (1) . The exploration of this phenomenon is the main motivation for our research on F -C ompletion . In this article, we prove that completions into several well-studied classes of graphs without long induced cycles and paths also admit parameterized subexponential time algorithms by showing that: —The problem T rivially P erfect C ompletion , which is F - C ompletion for F ={ C 4 , P 4 }, a cycle and a path on four vertices, is solvable in parameterized subexponential time 2 O (√ k log k ) n O (1) . —The problems known in the literature as P seudosplit C ompletion , the case in which F{2 K 2 , C 4 }, and T hreshold C ompletion , in which F =2 K 2 , P 4 , C 4 }, are also solvable in time 2 O (√ k log k ) n O }(1) . We complement our algorithms for F -C ompletion with the following lower bounds: —For F ={2 K 2 }, F = { C 4 }, F ={ P o 4 }, and F ={2 K 2 , P 4 }, F -C ompletion cannot be solved in time 2 o(k) n O (1) unless the Exponential Time Hypothesis (ETH) fails. Our upper and lower bounds provide a complete picture of the subexponential parameterized complexity of F -C ompletion problems for any F ⊆ {2 K 2 , C 4 , P 4 }.
    Type of Medium: Online Resource
    ISSN: 1942-3454 , 1942-3462
    URL: Article
    DOI: 10.1145/2799640
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2015
    detail.hit.zdb_id: 2488065-6
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...