• norsk
    • English
  • norsk 
    • norsk
    • English
  • Logg inn
Vis innførsel 
  •   Hjem
  • University of Bergen Library
  • Registrations from Cristin
  • Vis innførsel
  •   Hjem
  • University of Bergen Library
  • Registrations from Cristin
  • Vis innførsel
JavaScript is disabled for your browser. Some features of this site may not work without it.

Path contraction faster than $2^n$

Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar
Journal article, Peer reviewed
Published version
Thumbnail
Åpne
PDF (5.617Mb)
Permanent lenke
https://hdl.handle.net/11250/2755454
Utgivelsesdato
2020
Metadata
Vis full innførsel
Samlinger
  • Department of Informatics [754]
  • Registrations from Cristin [5646]
Originalversjon
SIAM Journal on Discrete Mathematics. 2020, 34(2), 1302–1325   10.1137/19M1259638
Sammendrag
A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs $\cal F$, the $\mathcal{F}$-Contraction problem takes as input a graph $G$ on $n$ vertices, and the objective is to output the largest integer $t$, such that $G$ is contractible to a graph $H \in {\cal F}$, where $|V(H)|=t$. When $\cal F$ is the family of paths, then the corresponding $\mathcal{F}$-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time $2^{n}\cdot n^{{\mathcal{O}}(1)}$. In spite of the deceptive simplicity of the problem, beating the $2^{n}\cdot n^{{\mathcal{O}}(1)}$ bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time ${{1.99987}^n}\cdot n^{{\mathcal O}(1)}$. We also define a problem called 3-Disjoint Connected Subgraphs and design an algorithm for it that runs in time $1.88^n\cdot n^{{\mathcal O}(1)}$. The above algorithm is used as a subroutine in our algorithm for Path Contraction.
Utgiver
SIAM
Tidsskrift
SIAM Journal on Discrete Mathematics
Opphavsrett
Copyright 2020 Society for Industrial and Applied Mathematics

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit
 

 

Bla i

Hele arkivetDelarkiv og samlingerUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifterDenne samlingenUtgivelsesdatoForfattereTitlerEmneordDokumenttyperTidsskrifter

Min side

Logg inn

Statistikk

Besøksstatistikk

Kontakt oss | Gi tilbakemelding

Personvernerklæring
DSpace software copyright © 2002-2019  DuraSpace

Levert av  Unit