Imagen de Portada

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Chiu, Yung-Chung, Lu, Hsueh-I
Formato:	Preprint
Publicado:	2021
Materias:	Data Structures and Algorithms Discrete Mathematics 05C38, 05C10, 05C85, 68P05
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
por: Liao, I-Cheng, et al.
Publicado: (2023)

A simple quadratic kernel for Token Jumping on surfaces
por: Cranston, Daniel W., et al.
Publicado: (2024)

Graph Burning: Bounds and Hardness
por: Antony, Dhanyamol, et al.
Publicado: (2024)

On the joint embedding property for cographs and trees
por: Carter, Daniel
Publicado: (2024)

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
por: Masařík, Tomáš, et al.
Publicado: (2026)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
por: Jelínek, Vít, et al.
Publicado: (2020)

Induced Minor Models. I. Structural Properties and Algorithmic Consequences
por: Bousquet, Nicolas, et al.
Publicado: (2024)

Reconfiguring homomorphisms to reflexive graphs via a simple reduction
por: Mühlenthaler, Moritz, et al.
Publicado: (2024)

Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
por: Baste, Julien, et al.
Publicado: (2019)

The Complexity of Distance-$r$ Dominating Set Reconfiguration
por: Banerjee, Niranka, et al.
Publicado: (2023)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
por: Lima, Paloma T., et al.
Publicado: (2024)

More relations between $λ$-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
por: Zaker, Manouchehr
Publicado: (2021)

Young domination on Hamming rectangles
por: Gravner, Janko, et al.
Publicado: (2025)

Branch-width of connectivity functions is fixed-parameter tractable
por: Korhonen, Tuukka, et al.
Publicado: (2026)

Excluding a Forest Induced Minor
por: Bonnet, Édouard, et al.
Publicado: (2025)

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
por: Milanič, Martin, et al.
Publicado: (2024)

Pathographs and some (un)decidability results
por: Carter, Daniel, et al.
Publicado: (2025)

Colorful Minors
por: Protopapas, Evangelos, et al.
Publicado: (2025)

$K_2$-Hamiltonian Graphs: II
por: Goedgebeur, Jan, et al.
Publicado: (2023)

Tree independence number V. Walls and claws
por: Chudnovsky, Maria, et al.
Publicado: (2025)

Excluding an induced wheel minor in graphs without large induced stars
por: Choi, Mujin, et al.
Publicado: (2025)

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
por: Dallard, Clément, et al.
Publicado: (2024)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
por: Munaro, Andrea, et al.
Publicado: (2022)

Generation and New Infinite Families of $K_2$-hypohamiltonian Graphs
por: Goedgebeur, Jan, et al.
Publicado: (2023)

The Upper Clique Transversal Problem
por: Milanič, Martin, et al.
Publicado: (2023)

Optimal Bounds for the k-Disjoint Paths Problem
por: Cavallaro, Dario, et al.
Publicado: (2026)

Conformality of Minimal Transversals of Maximal Cliques
por: Boros, Endre, et al.
Publicado: (2024)

Awesome graph parameters
por: Štorgel, Kenny Bešter, et al.
Publicado: (2025)

Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem
por: Boros, Endre, et al.
Publicado: (2023)

The strong vertex span of trees
por: Grašič, Mateja, et al.
Publicado: (2024)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
por: Patzner, Julian, et al.
Publicado: (2024)

Killing a Vortex
por: Thilikos, Dimitrios M., et al.
Publicado: (2022)

An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
por: Mkrtchyan, Vahan
Publicado: (2024)

Solving the Graph Burning Problem for Large Graphs
por: Pereira, Felipe de Carvalho, et al.
Publicado: (2024)

Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
por: Furmańczyk, Hanna, et al.
Publicado: (2020)

Edge open packing: complexity, algorithmic aspects, and bounds
por: Brešar, Boštjan, et al.
Publicado: (2024)

Small-scale operations on graphic sequences
por: Rusu, Irena
Publicado: (2026)

Symmetry classes of Hamiltonian cycles
por: Baligacs, Julia, et al.
Publicado: (2025)

Isolation critical graphs under multiple edge subdivision
por: Bartolo, Karl, et al.
Publicado: (2026)

W-state graphs: Structure and Algorithms
por: Gajjala, Rishikesh, et al.
Publicado: (2026)