Vangelis Th. Paschos

According to our database1, Vangelis Th. Paschos authored at least 157 papers between 1991 and 2019.

Collaborative distances:

Book
In proceedings
Article
PhD thesis
Other

Bibliography

2019
Preface to Special Issue on Algorithms and Complexity.
Theor. Comput. Sci., 2019

Structural parameters, tight bounds, and approximation for (k, r)-center.
Discret. Appl. Math., 2019

New Algorithms for Mixed Dominating Set.
CoRR, 2019

A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs.
CoRR, 2019

Average-case complexity of a branch-and-bound algorithm for min dominating set.
CoRR, 2019

Improved (In-)Approximability Bounds for d-Scattered Set.
Proceedings of the Approximation and Online Algorithms - 17th International Workshop, 2019

2018
The many facets of upper domination.
Theor. Comput. Sci., 2018

Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7.
RAIRO - Operations Research, 2018

J. Comput. Syst. Sci., 2018

Purely combinatorial approximation algorithms for maximum k-vertex cover in bipartite graphs.
Discret. Optim., 2018

The probabilistic minimum dominating set problem.
Discret. Appl. Math., 2018

When polynomial approximation meets exact computation.
Annals OR, 2018

Sparsification and subexponential approximation.
Acta Informatica, 2018

Structurally Parameterized d-Scattered Set.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

Multistage Matchings.
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory, 2018

Differential Ratio Approximation.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

Reductions That Preserve Approximability.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics, 2018

2017
Dual parameterization and parameterized approximability of subset graph problems.
RAIRO - Operations Research, 2017

Exact and superpolynomial approximation algorithms for the densest k-subgraph problem.
Eur. J. Oper. Res., 2017

2016
Super-polynomial approximation branching algorithms.
RAIRO - Operations Research, 2016

Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems.
RAIRO Theor. Informatics Appl., 2016

Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs.
Proceedings of the LATIN 2016: Theoretical Informatics, 2016

Upper Domination: Complexity and Approximation.
Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

Algorithmic Aspects of Upper Domination: A Parameterised Perspective.
Proceedings of the Algorithmic Aspects in Information and Management, 2016

2015
New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set.
Theory Comput. Syst., 2015

On the max min vertex cover problem.
Discret. Appl. Math., 2015

Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio~0.7.
CoRR, 2015

Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n, p)$ random model.
CoRR, 2015

Algorithmic Aspects of Upper Domination.
CoRR, 2015

Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization.
Algorithmica, 2015

On Subexponential and FPT-Time Inapproximability.
Algorithmica, 2015

2014
Special Issue: "Combinatorial Optimization: Theory of Algorithms and Complexity".
Theor. Comput. Sci., 2014

Approximating MAX SAT by moderately exponential and parameterized algorithms.
Theor. Comput. Sci., 2014

Parameterized (in)approximability of subset problems.
Oper. Res. Lett., 2014

Efficient algorithms for the max k-vertex cover problem.
J. Comb. Optim., 2014

On the approximation of maximum $k$-vertex cover in bipartite graphs.
CoRR, 2014

2013
Preface.
Theor. Comput. Sci., 2013

Reoptimization of maximum weight induced hereditary subgraph problems.
Theor. Comput. Sci., 2013

Exponential approximation schemata for some network design problems.
J. Discrete Algorithms, 2013

Reoptimization under Vertex Insertion: Max PK-Free Subgraph and Max Planar Subgraph.
Discrete Math., Alg. and Appl., 2013

Weighted completion time minimization on a single-machine with a fixed non-availability interval: Differential approximability.
Discret. Optim., 2013

Fast algorithms for min independent dominating set.
Discret. Appl. Math., 2013

Playing with Parameters: Cross-parameterization in Graphs.
CoRR, 2013

Multiparameterizations for max $k$-set cover and related satisfiability problems.
CoRR, 2013

Exact and Approximation Algorithms for Densest k-Subgraph.
Proceedings of the WALCOM: Algorithms and Computation, 7th International Workshop, 2013

Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization.
Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

The Probabilistic Min Dominating Set Problem.
Proceedings of the Computer Science - Theory and Applications, 2013

2012
Algorithms for dominating clique problems.
Theor. Comput. Sci., 2012

On the probabilistic min spanning tree Problem.
J. Math. Model. Algorithms, 2012

The max quasi-independent set problem.
J. Comb. Optim., 2012

Online maximum k-coverage.
Discret. Appl. Math., 2012

Subexponential and FPT-time Inapproximability of Independent Set and Related Problems
CoRR, 2012

Fast Algorithms for max independent set.
Algorithmica, 2012

Reoptimization of the Maximum Weighted P k -Free Subgraph Problem under Vertex Insertion.
Proceedings of the WALCOM: Algorithms and Computation - 6th International Workshop, 2012

Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

New Results on Polynomial Inapproximability and Fixed Parameter Approximability of edge dominating set.
Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011
A survey on combinatorial optimization in dynamic environments.
RAIRO - Operations Research, 2011

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms.
Discret. Appl. Math., 2011

2010
Approximating the max-edge-coloring problem.
Theor. Comput. Sci., 2010

Probabilistic models for the Steiner Tree problem.
Networks, 2010

Fast reoptimization for the minimum spanning tree problem.
J. Discrete Algorithms, 2010

On the max-weight edge coloring problem.
J. Comb. Optim., 2010

A survey on the structure of approximation classes.
Comput. Sci. Rev., 2010

Probabilistic optimization in graph-problems.
Algorithmic Oper. Res., 2010

Approximating the metric 2-Peripatetic Salesman Problem.
Algorithmic Oper. Res., 2010

Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537n){\mathcal O}(1.08537^n).
Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

A Bottom-Up Method and Fast Algorithms for max independent set.
Proceedings of the Algorithm Theory, 2010

Fast Algorithms for min independent dominating set.
Proceedings of the Structural Information and Communication Complexity, 2010

2009
Efficient approximation of min set cover by moderately exponential algorithms.
Theor. Comput. Sci., 2009

Reoptimization of minimum and maximum traveling salesman's tours.
J. Discrete Algorithms, 2009

Probabilistic graph-coloring in bipartite and split graphs.
J. Comb. Optim., 2009

Approximation of min coloring by moderately exponential algorithms.
Inf. Process. Lett., 2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation.
Discret. Appl. Math., 2009

Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2.
Discret. Appl. Math., 2009

Max Edge Coloring of Trees
CoRR, 2009

Fast Algorithms for Max Independent Set in Graphs of Small Average Degree
CoRR, 2009

Simple and Fast Reoptimizations for the Steiner Tree Problem.
Algorithmic Oper. Res., 2009

Greedy Algorithms For On-Line Set-Covering.
Algorithmic Oper. Res., 2009

Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

Exact Algorithms for Dominating Clique Problems.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

2008
Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems.
Oper. Res., 2008

On the Maximum Edge Coloring Problem.
Proceedings of the Approximation and Online Algorithms, 6th International Workshop, 2008

An O*(1.0977n) Exact Algorithm for max independent set in Sparse Graphs.
Proceedings of the Parameterized and Exact Computation, Third International Workshop, 2008

Vertex-Uncertainty in Graph-Problems.
Proceedings of the Combinatorial Optimization and Applications, 2008

Combinatorial Optimization and Theoretical Computer Science - Interfaces and Perspectives: 30th Anniversary of the LAMSADE.
Wiley, ISBN: 978-1-8482-1021-9, 2008

2007
Differential Ratio Approximation.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Reductions That Preserve Approximability.
Proceedings of the Handbook of Approximation Algorithms and Metaheuristics., 2007

Time slot scheduling of compatible jobs.
J. Sched., 2007

An exact algorithm for MAX-CUT in sparse graphs.
Oper. Res. Lett., 2007

Improved worst-case complexity for the MIN 3-SET COVERING problem.
Oper. Res. Lett., 2007

Differential approximation of min sat.
Eur. J. Oper. Res., 2007

On the Performance of Congestion Games for Optimum Satisfiability Problems.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Steiner Forests on Stochastic Metric Graphs.
Proceedings of the Combinatorial Optimization and Applications, 2007

2006
Completeness in approximation classes beyond APX.
Theor. Comput. Sci., 2006

On-line models and algorithms for max independent set.
RAIRO - Operations Research, 2006

Weighted Coloring: further complexity and approximability results.
Inf. Process. Lett., 2006

Jon Lee, A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics.
Eur. J. Oper. Res., 2006

Reductions, completeness and the hardness of approximability.
Eur. J. Oper. Res., 2006

Approximation algorithms for 2-Peripathetic Salesman Problem with edge weights 1 and 2.
Electron. Notes Discret. Math., 2006

On the probabilistic minimum coloring and minimum k-coloring.
Discret. Appl. Math., 2006

Greedy algorithms for on-line set-covering and related problems.
Proceedings of the Theory of Computing 2006, 2006

2005
On-line vertex-covering.
Theor. Comput. Sci., 2005

On the differential approximation of MIN SET COVER.
Theor. Comput. Sci., 2005

Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness.
Theor. Comput. Sci., 2005

Improved Approximations for Weighted and Unweighted Graph Problems.
Theory Comput. Syst., 2005

On-line maximum-order induced hereditary subgraph problems.
Int. Trans. Oper. Res., 2005

Completeness in differential approximation classes.
Int. J. Found. Comput. Sci., 2005

Proving completeness by logic.
Int. J. Comput. Math., 2005

Polynomial approximation algorithms with performance guarantees: An introduction-by-example.
Eur. J. Oper. Res., 2005

A hypocoloring model for batch scheduling.
Discret. Appl. Math., 2005

Greedy Differential Approximations for Min Set Cover.
Proceedings of the SOFSEM 2005: Theory and Practice of Computer Science, 2005

Computing Optimal Solutions for the min 3-set covering Problem.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Differential Approximation of min sat, max sat and Related Problems.
Proceedings of the Computational Science and Its Applications, 2005

Probabilistic Coloring of Bipartite and Split Graphs.
Proceedings of the Computational Science and Its Applications, 2005

2004
Lower Bounds on the Approximation Ratios of Leading Heuristics for the Single-Machine Total Tardiness Problem.
J. Sched., 2004

Local approximations for maximum partial subgraph problem.
Oper. Res. Lett., 2004

Algorithms for the On-Line Quota Traveling Salesman Problem.
Inf. Process. Lett., 2004

Approximation preserving reductions for set covering, vertex covering and independent set hierarchies under differential approximation.
Int. J. Comput. Math., 2004

A simulated annealing approach for the circular cutting problem.
Eur. J. Oper. Res., 2004

The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003
Optima locaux garantis pour l'approximation différentielle.
Tech. Sci. Informatiques, 2003

Approximation algorithms for the traveling salesman problem.
Math. Methods Oper. Res., 2003

Differential approximation results for the traveling salesman problem with distances 1 and 2.
Eur. J. Oper. Res., 2003

Differential approximation for optimal satisfiability and related problems.
Eur. J. Oper. Res., 2003

Polynomial Approximation and Graph-Coloring.
Computing, 2003

Differential approximation results for the Steiner tree problem.
Appl. Math. Lett., 2003

The Probabilistic Minimum Coloring Problem.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2003

2002
A priori optimization for the probabilistic maximum independent set problem.
Theor. Comput. Sci., 2002

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances.
RAIRO - Operations Research, 2002

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation.
RAIRO - Operations Research, 2002

Weighted Node Coloring: When Stable Sets Are Expensive.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

Algorithms and Models for the On-Line Vertex-Covering.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2002

2001
On-line independent set by coloring vertices.
Oper. Res., 2001

2000
Master-Slave Strategy and Polynomial Approximation.
Comp. Opt. and Appl., 2000

On-Line Maximum-Order Induces Hereditary Subgraph Problems.
Proceedings of the SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25, 2000

1999
Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems.
RAIRO - Operations Research, 1999

An improved general procedure for lexicographic bottleneck problems.
Oper. Res. Lett., 1999

The probabilistic longest path problem.
Networks, 1999

1998
Differential Approximation Algorithms for Some Combinatorial Optimization Problems.
Theor. Comput. Sci., 1998

Average-Case Complexity for the Execution of Recursive Definitions on Relational Databases.
Acta Informatica, 1998

1997
A Survey of Approximately Optimal Solutions to Some Covering and Packing Problems.
ACM Comput. Surv., 1997

The Approximability Behaviour of Some Combinatorial Problems with Respect to the Approximability of a Class of Maximum Independent Set Problems.
Comp. Opt. and Appl., 1997

A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts.
Annals OR, 1997

1996
On an Approximation Measure Founded on the Links Between Optimization and Polynomial Approximation Theory.
Theor. Comput. Sci., 1996

1995
Average Case Analysis of Greedy Algorithms for Optimisation Problems on Set Systems.
Theor. Comput. Sci., 1995

Constructive - Non-constructive Approximation and Maximum Independent Set Problem.
Proceedings of the Combinatorics and Computer Science, 1995

1994
Approximation Results for the Minimum Graph Coloring Problem.
Inf. Process. Lett., 1994

1992
A (Delta/2)-Approximation Algorithm for the Maximum Independent Set Problem.
Inf. Process. Lett., 1992

Evaluation of the Execution Cost of Recursive Definitions.
Comput. J., 1992

Average Case Analysis of a Greedy Algorithm for the Minimum Hitting Set Problem.
Proceedings of the LATIN '92, 1992

1991
On the Approximation of NP-Complete Problems by Using the Boltzmann Machine Method: The Cases of Some Covering and Packing Problems.
IEEE Trans. Computers, 1991

On the Mean Execution Time of Recursive Definitions on Relational Databases.
Proceedings of the MFDBS 91, 1991

On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-Colored Complete Graphs.
Proceedings of the ISA '91 Algorithms, 1991

A Theorem on the Approximation of Set Cover and Vertex Cover.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991