Finding even subgraphs even faster

DOI10.1016/j.jcss.2018.03.001zbMath1404.68050arXiv1409.4935OpenAlexW2143456777WikidataQ129921166 ScholiaQ129921166MaRDI QIDQ1671994

Pranabendu Misra, Prachi Goyal, Fahad Panolan, Saket Saurabh, Geevarghese Philip

Publication date: 7 September 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.4935

zbMATH Keywords

dynamic programmingFPT algorithmrepresentative familyco-graphic matroidEulerian edge deletion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Building large \(k\)-cores from sparse graphs ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Editing to Connected F-Degree Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of connected even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems
• A parameterized view on matroid optimization problems
• On Eulerian extensions and their application to no-wait flowshop scheduling
• Parameterized complexity of Eulerian deletion problems
• Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
• Deterministic Truncation of Linear Matroids
• Editing to Connected f-Degree Graph
• Matching, Euler tours and the Chinese postman
• Efficient Algorithms for Eulerian Extension and Rural Postman
• Multiplying matrices faster than coppersmith-winograd
• Spectral Theory and Analysis
• Long Circuits and Large Euler Subgraphs

This page was built for publication: Finding even subgraphs even faster