Balanced substructures in bicolored graphs

DOI10.1007/978-3-031-23101-8_12MaRDI QIDQ6169522zbMATH OpenFDO

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

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-23101-8_12

zbMATH Keywords

balanced subgraphsedge-colored graphsparameterized 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)

Recommendations

• Algorithms and hardness results for the maximum balanced connected subgraph problem
• Complexity and inapproximability results for balanced connected subgraph problem
• Balanced connected subgraph problem in geometric intersection graphs

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
• Graph theory
• 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
• LIMITS and applications of group algebras for parameterized problems
• 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: 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

Cited in

(1)

• The structural complexity landscape of finding balance-fair shortest paths

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 Q6169522)