Parameterized complexity of connected even/odd subgraph problems

DOI10.1016/J.JCSS.2013.07.002zbMATH Open1311.68075OpenAlexW2154257407WikidataQ60488404 ScholiaQ60488404MaRDI QIDQ395000FDOQ395000

Authors Fedor V. Fomin, Petr A. Golovach

Publication date 28 January 2014

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

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2012/3398/

zbMATH Keywords

treewidthparameterized complexityeven graphodd graphEuler graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• Parameterized complexity of connected even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of connected induced subgraph problems
• Parameterized complexity of finding connected induced subgraphs
• The parameterised complexity of counting even and odd induced subgraphs
• Parallel Complexity of the Connected Subgraph Problem
• On the complexity of some subgraph problems
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• The parameterised complexity of counting connected subgraphs and graph motifs

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Color-coding
• Counting subgraphs via homomorphisms
• Eulerian graphs and related topics. Part 1, Volume 1
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of even/odd subgraph problems
• Parametrized complexity theory.

Cited in

(7)

• Parameterized complexity of connected even/odd subgraph problems
• Flows and parity subgraphs of graphs with large odd-edge-connectivity
• Finding even subgraphs even faster
• Parameterized complexity of finding connected induced subgraphs
• Parallel Complexity of the Connected Subgraph Problem
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems

This page was built for publication: Parameterized complexity of connected even/odd subgraph problems

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