Editing to Connected F-Degree Graph

DOI10.1137/17M1129428zbMath1429.68189OpenAlexW2943900906MaRDI QIDQ5232130

Saket Saurabh, Fahad Panolan, Petr A. Golovach, Fedor V. Fomin

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1129428

zbMATH Keywords

matroidsrepresentative familycolor codingFTPconnected \(f\)-factorgraph editing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Building large \(k\)-cores from sparse graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Graph factors and factorization: 1985--2003: a survey
• A parameterized view on matroid optimization problems
• Eulerian graphs and related topics. Part 1, Volume 1
• Finding even subgraphs even faster
• Connected factors in graphs -- a survey
• Editing to a connected graph of given degrees
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• A Remark on Stirling's Formula
• Deterministic Truncation of Linear Matroids
• Fast FAST
• Factors and factorizations of graphs—a survey
• An algorithmic proof of Tutte's f-factor theorem
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Multiplying matrices faster than coppersmith-winograd
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable

This page was built for publication: Editing to Connected F-Degree Graph