Balanced substructures in bicolored graphs

DOI10.1016/J.TCS.2026.115745MaRDI QIDQ6858873zbMATH OpenFDO

Authors P. S. Ardra, R. Krithika, Saket Saurabh, Roohani Sharma

Publication date 12 February 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115745

zbMATH Keywords

balanced connected subgraphsedge coloringparameterized complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Algorithms and hardness results for the maximum balanced connected subgraph problem
• Balanced connected subgraph problem in geometric intersection graphs
• Color-coding
• Complexity and inapproximability results for balanced connected subgraph problem
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Highly connected monochromatic subgraphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Kernelization lower bounds through colors and IDs
• Large monochromatic components of small diameter
• LIMITS and applications of group algebras for parameterized problems
• Maximum degree and fractional matchings in uniform hypergraphs
• On generalized graphs
• On problems without polynomial kernels
• On zero-sum spanning trees and zero-sum connectivity
• Parameterized algorithms
• Representative families: a unified tradeoff-based approach
• Steiner trees, connected domination and strongly chordal graphs
• The balanced connected subgraph problem
• The balanced connected subgraph problem: complexity results in bounded-degree and bounded-diameter graphs
• The recognition of bound quivers using edge-coloured homomorphisms
• The Rectilinear Steiner Tree Problem is NP-Complete

This page was built for publication: Balanced substructures in bicolored graphs

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