Imagen de Portada

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Xiao, Chenglong, Mao, Chengyong, Wang, Shanshan
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Discrete Mathematics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
por: Galby, Esther, et al.
Publicado: (2025)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
por: An, Shinwoo, et al.
Publicado: (2025)

Constant delay Gray code enumeration of ideals and antichains in posets
por: Brenner, Sofia, et al.
Publicado: (2026)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
por: Deák, Bence, et al.
Publicado: (2026)

Counting random $k$-SAT near the satisfiability threshold
por: Chen, Zongchen, et al.
Publicado: (2024)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
por: Arkhipov, Pavel, et al.
Publicado: (2024)

Online Graph Coloring for $k$-Colorable Graphs
por: Kawarabayashi, Ken-ichi, et al.
Publicado: (2025)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
por: Bernshteyn, Anton, et al.
Publicado: (2024)

Random local access for sampling k-SAT solutions
por: Dong, Dingding, et al.
Publicado: (2024)

Improved Streaming Algorithm for Fair $k$-Center Clustering
por: Guo, Longkun, et al.
Publicado: (2025)

The complexity of strong conflict-free vertex-connection $k$-colorability
por: Hsieh, Sun-Yuan, et al.
Publicado: (2024)

On the enumeration of signatures of XOR-CNF's
por: Creignou, Nadia, et al.
Publicado: (2024)

On the number of $k$-mers admitting a given lexicographical minimizer
por: Ingels, Florian, et al.
Publicado: (2024)

Largest common subgraph of two forests
por: Rautenbach, Dieter, et al.
Publicado: (2024)

Thin Trees via $k$-Respecting Cut Identities
por: Daga, Mohit
Publicado: (2025)

$O(n +f(k))$: Truly Linear FPT
por: Bumpus, Benjamin Merlin, et al.
Publicado: (2026)

Vigemers: on the number of $k$-mers sharing the same XOR-based minimizer
por: Ingels, Florian, et al.
Publicado: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
por: Deligkas, Argyrios, et al.
Publicado: (2025)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
por: Alecu, Bogdan, et al.
Publicado: (2024)

A 1/2-Approximation for Budgeted $k$-Submodular Maximization
por: Wang, Chenhao
Publicado: (2025)

Maximum $k$- vs. $\ell$-colourings of graphs
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2023)

On Tight Robust Coresets for $k$-Medians Clustering
por: Huang, Lingxiao, et al.
Publicado: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
por: Hirahara, Shuichi, et al.
Publicado: (2024)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
por: Hirahara, Shuichi, et al.
Publicado: (2025)

Solving the List Coloring Problem through a Branch-and-Price algorithm
por: Lucci, Mauro, et al.
Publicado: (2023)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
por: Bencs, Ferenc, et al.
Publicado: (2024)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
por: Gawrychowski, Paweł, et al.
Publicado: (2024)

Approximation algorithms for non-sequential star packing problems
por: Hu, Mengyuan, et al.
Publicado: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2024)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
por: Tan, Jingjing
Publicado: (2024)

Fast approximation algorithms for the 1-median problem on real-world large graphs
por: Ueta, Keisuke, et al.
Publicado: (2025)

A column generation algorithm for finding co-3-plexes in chordal graphs
por: Dupont-Bouillard, Alexandre
Publicado: (2026)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
por: Foucaud, Florent, et al.
Publicado: (2025)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
por: Iwata, Satoru, et al.
Publicado: (2024)

On graphs coverable by k shortest paths
por: Dumas, Maël, et al.
Publicado: (2022)

Searching in trees with $k$-up-modular cost functions
por: Szyfelbein, Michał
Publicado: (2025)

Designing sparse temporal graphs satisfying connectivity requirements
por: Bellitto, Thomas, et al.
Publicado: (2026)

Parameterised algorithms for temporally satisfying reconfiguration problems
por: Davot, Tom, et al.
Publicado: (2025)

Efficient algorithms for the Potts model on small-set expanders
por: Carlson, Charles, et al.
Publicado: (2020)

Space-Efficient Hierholzer: Eulerian Cycles in $\mathrm{O}(m)$ Time and $\mathrm{O}(n)$ Space
por: Alaoui, Ziad Ismaili, et al.
Publicado: (2025)