Results 41 to 50 of about 89 (87)
Hardness Results and Spectral Techniques for Combinatorial Problems on Circulant Graphs
, 1998 We show that computing (and even approximating) MAXIMUM CLIQUE and MINIMUM GRAPH COLORING for circulant graphs is essentially as hard as in the general case.
Ivan Gerace +5 more
core +1 more source
A $4/3$ Approximation for $2$-Vertex-Connectivity [PDF]
TheoretiCSThe 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph $G$.
Miguel Bosch-Calvo +2 more
doaj +1 more source
Super-polynomial approximation branching algorithms [PDF]
, 2016 International audienceWe give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 ± , for arbitrarily small) for broad classes of combinatorial optimization ...
Emeric Tourniaire +5 more
core +1 more source
The generalizedp-Centdian on network
Location, Centdian, Networks, 68Q20, 68R99, 05C85, 90C35,
Dionisio Brito, José Moreno Pérez
core +1 more source
Faster parameterized algorithms for modification problems to minor-closed classes [PDF]
TheoretiCSLet ${\cal G}$ be a minor-closed graph class and let $G$ be an $n$-vertex graph. We say that $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$.
Laure Morelle +3 more
doaj +1 more source
Fast algorithms for determining (generalized) core groups in social networks
Core, Large network, Decomposition, Graph algorithm, 05A18, 05C70, 05C85, 05C90, 68R10, 68W40, 92H30, 92G30, 93A15,
Vladimir Batagelj, Matjaž Zaveršnik
core +1 more source
Load balancing for integer loads using a modified approach
ArrayLoad balancing plays a crucial role in improving the performance of distributed systems, where uneven task distribution often leads to poor resource utilisation and degraded system throughput.
Saumya Y.M., S.M. Hegde
doaj +1 more source
, 2008 We define the harmonic evolution of states of a graph by iterative application of the harmonic operator (Laplacian over Z2). This provides graphs with a new geometric context and leads to a new tool to analyze them.
Jerzy Kocik
core
The Serial Transitive Closure Problem for Trees
, 2002 The serial transitive closure problem is the problem of, given a directed graph G and a list of edges, called closure edges, which are in the transitive closure of the graph, to generate all the closure edges from edges in G.
core
Total-Chromatic Number and Chromatic Index of Dually Chordal Graphs
, 2007 A graph is dually chordal if it is the clique graph of a chordal graph. Alternatively, a graph is dually chordal if it admits a maximum neighbourhood order. This class generalizes known subclasses of chordal graphs such as doubly chordal graphs, strongly
Celina M. H. De Figueiredo +3 more
core