Separator-based data reduction for signed graph balancing

• Abu-Khzam FN, Collins RL, Fellows MR, Langston MA, Suters WH, Symons CT (2004) Kernelization algorithms for the vertex cover problem: Theory and experiments. In: Proceedings of the 6th workshop on algorithm engineering and experiments (ALENEX ’04). SIAM, pp 62–69

• Abu-Khzam FN, Fellows MR, Langston MA, Suters WH (2007) Crown structures for vertex cover kernelization. Theory Comput Syst 41(3):411–430

  Article  MATH  MathSciNet  Google Scholar 

• Agarwal A, Charikar M, Makarychev K, Makarychev Y (2005) \(O(\sqrt{\log n})\) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In: Proceedings of the 37th ACM symposium on theory of computing (STOC ’05). ACM, pp 573–581

• Antal T, Krapivsky PL, Redner S (2006) Social balance on networks: The dynamics of friendship and enmity. Physica D: Nonlinear Phenom 224(1–2):130–136

  Article  MATH  MathSciNet  Google Scholar 

• Avidor A, Langberg M (2007) The multi-multiway cut problem. Theor Comput Sci 377(1–3):35–42

  Article  MATH  MathSciNet  Google Scholar 

• Barahona F (1980) On the complexity of max cut. Tech Rep 186, IMAG, Université Joseph Fourier, Grenoble, France

• Barahona F (1982) On the computational complexity of Ising spin glass models. J Phys A: Math Gen 15(10):3241–3253

  Article  MathSciNet  Google Scholar 

• Barahona F, Ridha Mahjoub A (1989) Facets of the balanced (acyclic) induced subgraph polytope. Math Program 45(1–3):21–33

  Article  MATH  Google Scholar 

• Barvinok AI, Woods K (2003) Short rational generating functions for lattice point problems. J Am Math Soc 16(4):957–979

  Article  MATH  MathSciNet  Google Scholar 

• Bodlaender HL, Koster AMCA (2008) Combinatorial optimization on graphs of bounded treewidth. Comput J 51:255–269

  Article  MathSciNet  Google Scholar 

• Boginski V, Butenko S, Pardalos PM (2005) Statistical analysis of financial networks. Comput Stat Data Anal 48(2):431–443

  Article  MATH  MathSciNet  Google Scholar 

• Boginski V, Butenko S, Pardalos PM (2006) Mining market data: A network approach. Comput Oper Res 33(11):3171–3184

  Article  MATH  Google Scholar 

• Boros E, Hammer PL (1991) The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Ann Oper Res 33(3):151–180

  Article  MATH  MathSciNet  Google Scholar 

• Chen J, Kanj IA, Jia W (2001) Vertex cover: Further observations and further improvements. J Algorithms 41(2):280–301

  Article  MATH  MathSciNet  Google Scholar 

• Chiang C, Kahng AB, Sinha S, Xu X, Zelikovsky AZ (2007) Fast and efficient bright-field AAPSM conflict detection and correction. IEEE Trans Comput-Aided Des Integr Circ Syst 26(1):115–126

  Article  Google Scholar 

• Coleman T, Saunderson J, Wirth A (2008) A local-search 2-approximation for 2-correlation-clustering. In: Proceedings of the 16th annual European symposium on algorithms (ESA ’08). LNCS, vol 5193. Springer, Berlin, pp 308–319

  Google Scholar 

• DasGupta B, Enciso GA, Sontag ED, Zhang Y (2007) Algorithmic and complexity results for decompositions of biological networks into monotone subsystems. Biosystems 90(1):161–178

  Article  Google Scholar 

• Downey RG, Fellows MR (1999) Parameterized complexity. Springer, Berlin

  Google Scholar 

• Estivill-Castro V, Fellows MR, Langston MA, Rosamond FA (2006) FPT is P-time extremal structure I. In: Proceedings of the 1st algorithms and complexity in Durham workshop (ACiD ’06). Texts in Algorithmics, vol 4. College Publications, pp 1–41

• Feist AM, Scholten JCM, Palsson BØ, Brockman FJ, Ideker T (2006) Modeling methanogenesis with a genome-scale metabolic reconstruction of Methanosarcina barkeri. Mol Syst Biol 2:2006 .0004

  Article  Google Scholar 

• Fellows MR, Langston MA (1989) An analogue of the Myhill–Nerode theorem and its use in computing finite-basis characterizations. In: Proceedings of the 30th annual IEEE symposium on foundations of computer science (FOCS ’89). IEEE, pp 520–525

• Flum J, Grohe M (2006) Parameterized complexity theory. Springer, Berlin

  Google Scholar 

• Gabow HN (2000) Path-based depth-first search for strong and biconnected components. Inf Process Lett 74(3–4):107–114

  Article  MathSciNet  Google Scholar 

• Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145

  Article  MATH  MathSciNet  Google Scholar 

• Grötschel M, Pulleyblank WR (1981) Weakly bipartite graphs and the max-cut problem. Oper Res Lett 1(1):23–27

  Article  MATH  MathSciNet  Google Scholar 

• Guo J, Niedermeier R (2007) Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1):31–45

  Article  Google Scholar 

• Guo J, Hüffner F, Niedermeier R (2004) A structural view on parameterizing problems: Distance from triviality. In: Proceedings of the 1st international workshop on parameterized and exact computation (IWPEC ’04). LNCS, vol 3162. Springer, Berlin, pp 162–173

  Chapter  Google Scholar 

• Guo J, Gramm J, Hüffner F, Niedermeier R, Wernicke S (2006) Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J Comput Syst Sci 72(8):1386–1396

  Article  MATH  Google Scholar 

• Guo J, Moser H, Niedermeier R (2008) Iterative compression for exactly solving NP-hard minimization problems. In: Proceedings of the DFG SPP 1126 “algorithmics of large and complex networks”. LNCS. Springer, Berlin, to appear

• Gutwenger C, Mutzel P (2000) A linear time implementation of SPQR-trees. In: Proceedings of the 8th international symposium on graph drawing (GD ’00). LNCS, vol 1984. Springer, Berlin, pp 77–90

  Google Scholar 

• Harary F (1953) On the notion of balance of a signed graph. Michigan Math J 2(2):143–146

  Article  MathSciNet  Google Scholar 

• Harary F (1959) On the measurement of structural balance. Behav Sci 4(4):316–323

  Article  Google Scholar 

• Harary F, Lim MH, Wunsch DC (2002) Signed graphs for portfolio analysis in risk management. IMA J Manag Math 13(3):201–210

  Article  MATH  Google Scholar 

• Henzinger MR, Rao S, Gabow HN (2000) Computing vertex connectivity: New bounds from old techniques. J Algorithms 43(2):222–250

  Article  MathSciNet  Google Scholar 

• Hicks IV, Koster AMCA, Kolotoğlu E (2005) Branch and tree decomposition techniques for discrete optimization. In: TutORials 2005, tutorials in operations research, INFORMS, pp 1–29

• Hopcroft JE, Tarjan RE (1973) Dividing a graph into triconnected components. SIAM J Comput 2(3):135–158

  Article  MathSciNet  Google Scholar 

• Hüffner F (2005) Algorithm engineering for optimal graph bipartization. In: Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA ’05). LNCS, vol 3503. Springer, Berlin, pp 240–252. Extended version to appear in J Graph Algorithms Appl

  Chapter  Google Scholar 

• Hüffner F (2007) Algorithms and experiments for parameterized approaches to hard graph problems. PhD thesis, Institut für Informatik, Friedrich-Schiller-Universität Jena

• Hüffner F, Komusiewicz C, Moser H, Niedermeier R (2008) Fixed-parameter algorithms for cluster vertex deletion. In: Proceedings of the 8th Latin American theoretical informatics symposium (LATIN ’08). LNCS, vol 4598. Springer, Berlin, pp 711–722. Extended version to appear in Theory Comput Syst

  Chapter  Google Scholar 

• Khot S (2002) On the power of unique 2-prover 1-round games. In: Proceedings of the 34th ACM symposium on theory of computing (STOC ’02). ACM, pp 767–775

• Kőnig D (1936) Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig, English translation: Theory of finite and infinite graphs, Birkhäuser, 1990

• Leroy X, Vouillon J, Doligez D et al (1996) The objective caml system. Available on the web, http://caml.inria.fr/ocaml/

• Makhorin A (2004) GNU linear programming kit reference manual version 4.8. Department of Applied Informatics, Moscow Aviation Institute

• Mi H, Lazareva-Ulitsky B, Loo R, Kejariwal A, Vandergriff J, Rabkin S, Guo N, Muruganujan A, Doremieux O, Campbell MJ, Kitano H, Thomas PD (2005) The PANTHER database of protein families, subfamilies, functions and pathways. Nucleic Acids Res 33(Supplement 1):284–288

  Google Scholar 

• Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, Oxford

  Book  MATH  Google Scholar 

• Oda K, Kitano H (2006) A comprehensive map of the toll-like receptor signaling network. Mol Syst Biol 2:2006.0015

  Article  Google Scholar 

• Oda K, Kimura T, Matsuoka Y, Funahashi A, Muramatsu M, Kitano H (2004) Molecular interaction map of a macrophage. AfCS Res Rep 2:14

  Google Scholar 

• Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425–440

  Article  MATH  MathSciNet  Google Scholar 

• Polzin T, Vahdati Daneshmand S (2006) Practical partitioning-based methods for the Steiner problem. In: Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA ’06). LNCS, vol 4007. Springer, Berlin, pp 241–252

  Google Scholar 

• Razgon I, O’Sullivan B (2008) Almost 2-SAT is fixed-parameter tractable. In: Proceedings of the 35th international colloquium on automata, languages and programming (ICALP ’08). LNCS, vol 5125. Springer, Berlin, pp 551–562

  Chapter  Google Scholar 

• Reed B, Smith K, Vetta A (2004) Finding odd cycle transversals. Oper Res Lett 32(4):299–301

  Article  MATH  MathSciNet  Google Scholar 

• Sturmfels B (1996) Gröbner bases and convex polytopes. University lecture series, vol 8. American Mathematical Society, Providence

  MATH  Google Scholar 

• Thagard P, Verbeurgt K (1998) Coherence as constraint satisfaction. Cogn Sci 22(1):1–24

  Article  Google Scholar 

• Volz E (2004) Random networks with tunable degree distribution and clustering. Phys Rev E 70(5):056115

  Article  Google Scholar 

• Wernicke S (2003) On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Diplomarbeit, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen

• Yannakakis M (1981) Edge-deletion problems. SIAM J Comput 10(2):297–309

  Article  MATH  MathSciNet  Google Scholar 

• Zaslavsky T (1998) Bibliography of signed and gain graphs. Electronic Journal of Combinatorics DS8, updated version available at http://www.math.binghamton.edu/zaslav/Bsg/

Download references