# Vangelis Th. Paschos

According to our database1, Vangelis Th. Paschos authored at least 177 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.
Discrete Applied Mathematics, 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

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

Time-approximation trade-offs for inapproximable problems.
J. Comput. Syst. Sci., 2018

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

The probabilistic minimum dominating set problem.
Discrete Applied Mathematics, 2018

When polynomial approximation meets exact computation.
Annals OR, 2018

Sparsification and subexponential approximation.
Acta Inf., 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

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.
European Journal of Operational Research, 2017

Structurally Parameterized $d$-Scattered Set.
CoRR, 2017

Structural Parameters, Tight Bounds, and Approximation for (k, r)-Center.
CoRR, 2017

Structural Parameters, Tight Bounds, and Approximation for (k, r)-Center.
Proceedings of the 28th International Symposium on Algorithms and Computation, 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. Inf. and Applic., 2016

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

Time-Approximation Trade-offs for Inapproximable Problems.
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.
Discrete Applied Mathematics, 2015

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

Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse.
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

Time-Approximation Trade-offs for Inapproximable Problems.
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

When polynomial approximation meets exact computation.
4OR, 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

Sparsification and subexponential approximation.
CoRR, 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.
Discrete Optimization, 2013

Fast algorithms for min independent dominating set.
Discrete Applied Mathematics, 2013

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

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

Parameterized (in)approximability of subset problems.
CoRR, 2013

Multi-parameter complexity analysis for constrained size graph problems: using greediness for parameterization.
CoRR, 2013

On the max min vertex cover Problem.
Proceedings of the Approximation and Online Algorithms - 11th International Workshop, 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

On Subexponential and FPT-Time Inapproximability.
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.
Discrete Applied Mathematics, 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

Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms.
Proceedings of the Theory and Applications of Models of Computation, 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

Efficient Algorithms for the max k -vertex cover Problem.
Proceedings of the Theoretical Computer Science, 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.
Discrete Applied Mathematics, 2011

Online Maximum k-Coverage.
Proceedings of the Fundamentals of Computation Theory - 18th International Symposium, 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.
Computer Science Review, 2010

Probabilistic optimization in graph-problems.
Algorithmic Operations Research, 2010

Approximating the metric 2-Peripatetic Salesman Problem.
Algorithmic Operations Research, 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

On the Probabilistic min spanning tree problem.
Proceedings of the International Multiconference on Computer Science and Information Technology, 2010

The max quasi-independent set Problem.
Proceedings of the Computer Science, 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.
Discrete Applied Mathematics, 2009

Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2.
Discrete Applied Mathematics, 2009

Fast algorithms for min independent dominating set
CoRR, 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 Operations Research, 2009

Greedy Algorithms For On-Line Set-Covering.
Algorithmic Operations Research, 2009

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

Approximating the Max Edge-Coloring Problem.
Proceedings of the Combinatorial Algorithms, 20th International Workshop, 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.
Operational Research, 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. Scheduling, 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.
European Journal of Operational Research, 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.
European Journal of Operational Research, 2006

Reductions, completeness and the hardness of approximability.
European Journal of Operational Research, 2006

Approximation algorithms for 2-Peripathetic Salesman Problem with edge weights 1 and 2.
Electronic Notes in Discrete Mathematics, 2006

On the probabilistic minimum coloring and minimum k-coloring.
Discrete Applied Mathematics, 2006

Reoptimization of Minimum and Maximum Traveling Salesman's Tours.
Proceedings of the Algorithm Theory, 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.
ITOR, 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.
European Journal of Operational Research, 2005

A hypocoloring model for batch scheduling.
Discrete Applied Mathematics, 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

Weighted Coloring: Further Complexity and Approximability Results.
Proceedings of the Theoretical Computer Science, 9th Italian Conference, 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. Scheduling, 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.
European Journal of Operational Research, 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

Algorithms for the On-Line Quota Traveling Salesman Problem.
Proceedings of the Computing and Combinatorics, 10th Annual International Conference, 2004

2003
Optima locaux garantis pour l'approximation différentielle.
Technique et Science Informatiques, 2003

Approximation algorithms for the traveling salesman problem.
Math. Meth. of OR, 2003

Differential approximation results for the traveling salesman problem with distances 1 and 2.
European Journal of Operational Research, 2003

Differential approximation for optimal satisfiability and related problems.
European Journal of Operational Research, 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

Completeness in Differential Approximation Classes.
Proceedings of the Mathematical Foundations of Computer Science 2003, 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.
Operational Research, 2001

Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2.
Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 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 Inf., 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