Losing Weight by Gaining Edges

Amir Abboud, Kevin Lewi, Ryan Williams

Type: Book-Chapter

Publication Date: 2014-01-01

Citations: 45

DOI: https://doi.org/10.1007/978-3-662-44777-2_1

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Losing Treewidth In The Presence Of Weights	2025	Michał Włodarczyk
+	The effect of edge weights on clique weights	2016	Raphael Yuster
+	Weighted Graphs	2020	Helmut Knebl
+	W2-graphs and shedding vertices	2017	Vadim E. Levit Eugen Mândrescu
+	Cutting up graphs	1982	M. J. Dunwoody
+	Changing upper irredundance by edge addition	2003	E. J. Cockayne Odile Favaron Wayne Goddard P.J.P. Grobler Christina M. Mynhardt
+ PDF Chat	Node-Balancing by Edge-Increments	2015	Friedrich Eisenbrand Shay Moran Rom Pinchasi Martin Skutella
+	Inducing W-graphs	2003	Robert B. Howlett Yunchuan Yin
+	Extremal graphs for weights	1999	Béla Bollobás P. Erdős Amites Sarkar
+	The Weight Function Lemma for graph pebbling	2016	Glenn Hurlbert
+	Expander Graphs	2013	Mike Krebs Anthony Shaheen
+ PDF Chat	Making Bidirected Graphs Strongly Connected	2019	Tatsuya Matsuoka Shun Sato
+	Conservative weightings and ear-decompositions of graphs	1993	András Frank
+	On weighted clique graphs	2010	Flavia Bonomo Jayme L. Szwarcfiter
+	Inducing W-graphs II	2004	Robert B. Howlett Yunchuan Yin
+	Decreasing the maximum degree of a graph	2022	Peter Borg
+ PDF Chat	Orienting edges to fight fire in graphs	2018	Julien Bensmail Nick Brettell
+ PDF Chat	Orienting edges to fight fire in graphs	2018	Julien Bensmail Nick Brettell
+	Perfectly Weighted Graphs	2001	Lawrence Brenton Lynda M. Jaje
+	Heavy cycles in weighted graphs	2005	Jun Fujisawa

Action	Title	Year	Authors
+	Consequences of APSP, triangle detection, and 3SUM hardness for separation between determinism and non-determinism	2021	Andrzej Lingas
+ PDF Chat	SETH-based Lower Bounds for Subset Sum and Bicriteria Path	2022	Amir Abboud Karl Bringmann Danny Hermelin Dvir Shabtay
+	Budgeted Dominating Sets in Uncertain Graphs	2021	Keerti Choudhary Avi Cohen N. S. Narayanaswamy David Peleg R. Vijayaragunathan
+ PDF Chat	On the Parameterized Complexity of Approximating Dominating Set	2019	C. S. Karthik Bundit Laekhanukit Pasin Manurangsi
+	On the Parameterized Complexity of Approximating Dominating Set	2017	C. S. Karthik Bundit Laekhanukit Pasin Manurangsi
+	Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal	2021	Karl Bringmann Jasper Slusallek
+ PDF Chat	On the parameterized complexity of approximating dominating set	2018	C. S. Karthik Bundit Laekhanukit Pasin Manurangsi
+	New Techniques for Proving Fine-Grained Average-Case Hardness	2020	Mina Dalirrooyfard Andrea Lincoln Virginia Vassilevska Williams
+ PDF Chat	All non-trivial variants of 3-LDT are equivalent	2020	Bartłomiej Dudek Paweł Gawrychowski Tatiana Starikovskaya
+ PDF Chat	On the Parameterized Intractability of Determinant Maximization	2024	Naoto Ohsaka

Action	Title	Year	Authors
+ PDF Chat	The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes	2014	David Cattanéo Simon Perdrix
+ PDF Chat	Finding and counting given length cycles	1997	Noga Alon Raphael Yuster Uri Zwick
+	Lower bounds for linear satisfiability problems	1995	Jeff Erickson
+ PDF Chat	Reducing a Target Interval to a Few Exact Queries	2012	Jesper Nederlof Erik Jan van Leeuwen Ruben van der Zwaan
+ PDF Chat	Exact Weight Subgraphs and the k-Sum Conjecture	2013	Amir Abboud Kevin Lewi
+ PDF Chat	Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems	2014	Amir Abboud Virginia Vassilevska Williams
+ PDF Chat	Sets of Integers that do not Contain Long Arithmetic Progressions	2011	Kevin O’Bryant
+ PDF Chat	Threesomes, Degenerates, and Love Triangles	2014	Allan Grønlund Seth Pettie
+	Finding an o(n ² log n) algorithm is sometimes hard	1996	Antonio Hernández Barrera