Editing to Connected F-Degree Graph

DOI10.1137/17M1129428MaRDI QIDQ5232130zbMATH OpenOpenAlexWikidataFDO

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

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

color codingconnected \(f\)-factorFTPgraph editing problemmatroidsrepresentative family

Mathematics Subject Classification ID

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

Recommendations

• Editing to connected f-degree graph
• Editing to a connected graph of given degrees
• Editing to a connected graph of given degrees
• Graph editing to a given degree sequence
• Graph editing to a given degree sequence
• Editing to a planar graph of given degrees
• Editing to a planar graph of given degrees
• Editing to Eulerian graphs
• Editing to Eulerian graphs
• Editing graphs to satisfy degree constraints: a parameterized approach

Cites work

• A parameterized view on matroid optimization problems
• A Remark on Stirling's Formula
• An algorithmic proof of Tutte's f-factor theorem
• Connected factors in graphs -- a survey
• Designing FPT algorithms for cut problems using randomized contractions
• Editing graphs to satisfy degree constraints: a parameterized approach
• Editing to a connected graph of given degrees
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Eulerian graphs and related topics. Part 1, Volume 1
• Factors and factorizations of graphs—a survey
• Fast FAST
• Finding even subgraphs even faster
• Fundamentals of parameterized complexity
• Graph factors and factorization: 1985--2003: a survey
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Matching theory
• Multiplying matrices faster than coppersmith-winograd
• Subexponential parameterized algorithm for minimum fill-in
• The minimum k-way cut of bounded size is fixed-parameter tractable

Cited in

(8)

• Graph editing to a given neighbourhood degree list is fixed-parameter tractable
• Editing to a connected graph of given degrees
• Building large \(k\)-cores from sparse graphs
• Editing to connected f-degree graph
• Graph editing to a given degree sequence
• Cograph editing: Merging modules is equivalent to editing P₄s
• A survey of parameterized algorithms and the complexity of edge modification
• Determinantal sieving

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232130)